# Enumerate all paths of length 3 in a given tree T

Kind help with an algorithm or any refrence to enumerate all paths of length 3 in a given tree T in the shortest possible time.

• Sounds like an interesting question. What did you try and where did you get stuck? – Juho Nov 26 '19 at 6:34
• Does length=3 refer to the number of vertices or edges? – Albjenow Nov 26 '19 at 14:49

Let $$T$$ be a tree on $$n$$ vertices. Root $$T$$ in an arbitrary vertex $$r$$ and let $$p(v)$$ denote the parent of vertex $$v \neq r$$ in $$T$$. For $$v \in V$$, let $$C(v)$$ denote the children of $$v$$ in $$T$$.

A path $$\langle v_1, v_2, v_3, v_4 \rangle$$ of length $$3$$ in $$T$$ is of exactly one of the following two forms (when the path's traversal direction is ignored):

• Type A: $$p(v_1) = v_2$$, $$p(v_2) = v_3$$, $$p(v_3) = v_4$$, or

• Type B: $$p(v_1)=p(v_3)=v_2$$ and $$p(v_4)=p(v_3)$$.

To enumerate all paths of type $$A$$ it suffices to perform a DFS visit of $$T$$. When a vertex $$v$$ at depth at least $$3$$ is encountered, return the path $$\langle v, p(v), p(p(v)), p(p(p(v))) \rangle$$. This takes $$O(n)$$ time overall.

To enumerate all paths of type $$B$$, perform a DFS visit of $$T$$ and when a vertex $$v$$ at depth at least $$2$$ is encountered, return all the paths of the form $$\langle v, p(v), p(p(v)), u \rangle$$ where $$u \in C(p(p(v))) \setminus \{ p(v) \}$$. This requires time $$O(n + P)$$, where $$P$$ is the number of paths of type $$B$$ in $$T$$.

Overall you can enumerate all the paths of length $$3$$ in $$T$$ in time $$O(n + P)$$.

Notice that $$\Omega(n)$$ is a lower bound on the time needed by any algorithm since you need to read the input tree. A bad case in which $$P=0$$ but you still spend $$\Theta(n)$$ time is a star.

• Thank you Could you help with with method or link on how to find the diametrical path of a Tree – sriram Nov 27 '19 at 15:08
• Right now I can only give the gist. But I'm sure you can find a description of how to solve that problem if you google. Anyway: Root the tree in an arbitrary vertex. Notice that there is a unique vertex of minimum depth in a diametral path $P$. Let this vertex be $v$. Then $P$ is the concatenation of two paths from $v$ to the deepest leaves in two distinct subtrees rooted in the children of $v$ (one or both of these paths might possibly be empty). Use a DFS visit to compute the length of such paths for all the nodes of $T$. This allows you to find $v$ and $P$. – Steven Nov 27 '19 at 22:34

I'm trying to solve it by white-gray-black DFS, but I failed to write the exact answer. But, this idea works: You can solve it easily by Adjacency Matrix Check this link: