Algorithm to get all paths in a tree

Question

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?

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.