CODEWITHSUNDEEP
algorithmdata-structurestree
Kohányi Róbert
Kohányi Róbert

Reputation: 10121

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

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.

Upvotes: 9

Views: 16976

Answers (4)

boiledwater
boiledwater

Reputation: 10482

1,Find leaf node
2,Up traversal from leaf node

public void printPath(N n) {
        if (n == null)
            return;
        if (n.left == null && n.right == null) {
            do {
                System.out.print(n.value);
                System.out.print(" ");
            } while ((n = n.parent) != null);
            System.out.println("");
            return;
        }
        printPath(n.left);
        printPath(n.right);
    }

printPath(Root);

Upvotes: 0

Marsellus Wallace
Marsellus Wallace

Reputation: 18601

Something that I came up with working on printing the words in a TrieTree that can be easily adaptable to other kinds of trees or different needs:

public void rootToLeaves() {
    HashMap<Integer, TrieNode> hashMap = new HashMap<Integer, TrieNode>();
    for(TrieNode trieNode : root.getChildren())
        rootToLeaves(trieNode, hashMap, 0);
}

private void rootToLeaves( TrieNode trieNode, HashMap<Integer, TrieNode> hashMap, int heightIndex ) {
    hashMap.put(heightIndex, trieNode);

    if( trieNode.isLeaf() )
        printValues(hashMap, heightIndex);
    else
        for( TrieNode childNode : trieNode.getChildren() )
            rootToLeaves( childNode, hashMap, heightIndex + 1 );
}

private void printValues(HashMap<Integer, TrieNode> hashMap, int heightIndex) {
    for(int index = 0; index <= heightIndex; index++)
        System.out.print(hashMap.get(index).getValue());
    System.out.println();
}

This solution does a nice job in terms of memory management (It uses a single HashMap whose size will never exceed the height of the tree) and it offers a lot of flexibility (Just replace printValues with whatever you need).

NOTE: Knowing the height of the tree in advance will let you use a simple Array instead of a Map.

Upvotes: 1

Dante May Code
Dante May Code

Reputation: 11247

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));
    }
  }
}

Upvotes: 10

BeeOnRope
BeeOnRope

Reputation: 64895

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.

Upvotes: 2

Related Questions