Algorithm to get all paths in a tree

Question

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

enter image description here

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?

• walpen: 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.
• Patrick Peer: 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' ;)
• Ordous: 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.

Answer 1

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
 add node to "discovered" list
 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.

• Tyress: 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