# Algorithm to get all paths in a tree

I have a tree that has n-levels. For example here I have four levels:

Each node has two children (except for the last one), however everyone except for the first and last node of each row has two parents. I'm trying to figure out a scalable way to get all paths into a List of Lists, so that for this example, I will have a List of Lists of chars:

``````A,B,D,G

A,B,D,H

A,B,E,H
``````

etc.

Can anyone help steer me to the right direction of finding an algorithm for this regardless of how many levels?

• As a sketch: perform depth-first-search and keep a list of paths, appending nodes to onto a path as you descend and copying portions of the path on backtracking. Jan 13, 2016 at 10:54
• Strictly speaking, this is not a tree, but a graph. See stackoverflow.com/questions/7423401/… and en.wikipedia.org/wiki/Tree_(graph_theory). With that in mind, you should find suiting algorithms by searching the web for 'graph traversal algorithms' ;) Jan 13, 2016 at 11:32
• Define "Scalable". The number of such paths is trivially `2^(n-1)` where `n` is the number of levels. Exponential amount of output is not typically called "scalable" or even "usable". What exactly are you trying to do with the paths? It's reasonably trivial to count the paths, and convert a path to it's number and back, for example. Jan 13, 2016 at 14:40

The fact that a node can have two parents shouldn't prevent you from using a standard depth first search. As you describe it, a child with two parents is still independently part of two "solutions". The fact that there are at most two edges leaving each node simplifies things further.

``````search(node):

if node is null: // maybe a non-terminal parent's left or right was null
return  // that or someone gave you a null graph

if node is terminal:
print the list //[A,B,D,G], [A,B,D,H], etc
remove node from the list
return // done at this level

search(node.left)
search(node.right)
remove node from the list // all done at this level
``````

You can change the order of discover by going right before you go left.

• I think this led me to the right direction, thanks! I just passed a "discovered" list as a parameter to the recursive function (creating new lists on the node.left and node.right fork) and printed that when it was a terminal node. Didn't have to remove the node from the list though Jan 14, 2016 at 7:00