2

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?

  • 2
    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. – walpen Jan 13 '16 at 10:54
  • 5
    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' ;) – Patrick Peer Jan 13 '16 at 11:32
  • 1
    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. – Ordous Jan 13 '16 at 14:40
4

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.

| improve this answer | |
  • 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 – Tyress Jan 14 '16 at 7:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.