Finding paths of certain length in trees In a graph tree, is there any "smart/existing/efficient" algorithm to find linear segments of defined length?

For example given a tree graph:

g = {1 -&gt; 2, 2 -&gt; 4, 3 -&gt; 6, 4 -&gt; 8, 6 -&gt; 12, 1 -&gt; 3, 2 -&gt; 5, 3 -&gt; 7, 
   4 -&gt; 9};
TreePlot[g, VertexLabeling -&gt; True]


 

How can one find all linear segments of length 4. In this example this would be 

1 2 4 8
1 2 4 9
1 3 6 12
2 1 3 7
2 1 3 6
9 4 2 5
...


This is probably a common problem, but I guess I have not yet found the right keywords for google. The naive implementation would be to visit every node, then recursively try to get four nodes away and delete all duplicated segments at the end...
Idea: Root the tree in an arbitrary node. For every node, count 


paths in its subtrees,
paths that start in a subtree and end in the root, and
paths that start in one subtree, traverse the root and end in another subtree.


That is, for a given node $v$ with children $u_1, \dots, u_m$, the number $p(v,k)$ of paths of length $k$ (counting nodes) in the subtree $T_v$ rooted in $v$ is

$\qquad\displaystyle\begin{align*}
  p(v,k) &amp;= \sum_{i=1}^m \biggl[ p(u_i,k) \biggr] \\
         &amp;\ + \sum_{i=1}^m \biggl[ p_r(u_i,k-1) \biggr] \\
         &amp;\ + \sum_{i=1}^{m-1}  \sum_{j=i+1}^m \sum_{l=1}^{k-2} \biggl[ p(u_i,l) \cdot p(u_j,k-1-l) \biggr] 
\end{align*}$

for $k \geq 2$; we anchor the recurrence in $p(v,1) = 1$ for all $v$. For the paths ending in the root, we get the (simpler) recurrence

$\qquad\begin{align*}
  p_r(v,k) &amp;= \sum_{i=1}^m p_r(u_i,k-1)
\end{align*}$

which also anchors in $p_r(v,1) = 1$. 

These recurrences immediately imply a recursive algorithm (computing both simultaneously). 

The runtime is in "$\Theta(m^2k)$" per node of degree $m$; hence, on trees with finitely bounded degree, the algorithm runs in time $\Theta(nk)$. Otherwise, it may take time $\Theta(n^2k)$ (e.g. on stars).