Traverse every unique path (from root to leaf) in an arbitrary tree structure

Question

I have several lists:

A = ["a0", "a1"]       // the number of lists varies
B = ["b0", "b1", "b2"] // such as the number of elements in a list.
C = ["c1"]
D = ["d0", "d1"]

I convert this structure into a tree:

             _____ROOT______
            /               \ 
       ___a0____        ____a1____
      /    |    \      /     |    \
    b0    b1    b2    b0    b1    b2
     |     |     |     |     |     |
    c1    c1    c1    c1    c1    c1
   / |   / |   / |   / |   / |   / |
  d0 d1 d0 d1 d0 d1 d0 d1 d0 d1 d0 d1

I'm printing every unique path in the tree (omitting the root):

a0 -> b0 -> c1 -> d0
a0 -> b0 -> c1 -> d1
a0 -> b1 -> c1 -> d0
...
a1 -> b2 -> c1 -> d1

I'm doing this by "destroying" the tree itself while traversing it in the following way:

public static void delete(Node node) {
  if (node.isLeaf() && !node.isRoot()) {
    Node parent = node.getParent();
    parent.removeChild(node);
    delete(parent);
  }
}

public static void traverse(Node node) {
  if (node.isRoot())
    System.out.println("---");
  else
    System.out.println(node.getName());

  if (node.isLeaf()) {    // I'm still working on
    if (!node.isRoot()) { // removing unnecessary checks
      delete(node);
      traverse(node.getRoot());
    }
  } else {
    Node child = node.firstChild();
    if (null != child)
      traverse(child);
  }
}      

traverse(Node) always prints the first available path of the tree (from root to leaf) while delete(Node) cuts leafs of the tree that is already visited by traverse(Node).

This works as intended, but I'm keen to find a solution to traverse the tree in the previously described way without destroying it. If there's a way to do this then I'd be interested to traverse this same structure, but in the form of a graph to reduce redundancy.

Answer 1

OK. I think you actually mean that you want to find every path from root to a leaf.

Then (a un-optimized version)

void traverse (Node root) {
  // assume root != NULL
  traverse (root, new LinkedList<Node>());
}

private void traverse (Node root, LinkedList<Node> path) {
  path.add(root);
  if (root.isLeaf()) {
    print path;
  }
  else {
    for each node of root {
      traverse (node, new LinkedList<Node>(path));
    }
  }
}

Answer 2

So basically you are doing a depth first search, but rather than tracking the visiting of the nodes explicitly in a non-destructive way, or maintaining enough context to search without tracking, you are destroying the tree to do this tracking.

The traditional way to convert this to a plain DFS would be to loop around your recursion condition, basically change the child recursive call to something like:

} else {
  for (Node child = node.firstChild(); node != null; node = node.nextChild()) {
      traverse(child);
  }
}

This will traverse all your children, and you can pretty much remove the node.isLeaf case, since backtracking is done automatically for you. Note that I made up the nextChild function since I can't see what it's called in your code, but you must have something similar, or some way to iterate through the children.

An alternate way that preserves more of the structure of your existing code would be to maintain a separate data structure which contains a set of "visited" nodes, this could be as simple as a Set of strings if all your node names are unique - rather than delete the node, add it to the "visited" set, and in your recursion condition, don't check for null, but rather find the first unvisited node. This is probably more complicated than the suggestion above, but might be more similar to what you have now - and would avoid loops in the case you ever need to do this on a cyclic graph rather than a tree.