Go through each unique path (from root to leaf) in an arbitrary tree structure

Question

I have a few 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 will convert this structure to 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 print every unique path in the tree (excluding the root):

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

I do this by "destroying" the tree itself while traversing it as follows:

 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 tree path (from root to leaf), and delete(Node) cuts the leaves of a tree that has already been visited by traverse(Node) .

This works as intended, but I really want to find a solution to cross the tree in the previously described way without destroying it. If there is a way to do this, I would be interested to go through the same structure, but in the form of a graph to reduce redundancy.

Answer 1

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

Then (not 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

Thus, basically you do the first depth search, and do not track the visits to nodes in an explicit non-destructive way or maintain sufficient context for the search without tracking, you destroy the tree for this tracking.

The traditional way to convert this to a simple DFS should be to loop your recursion condition, basically change the child's recursive call to something like:

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

This will get around all of your children, and you can pretty much remove the phrase node.isLeaf, as you are automatically traced backwards. Please note that I created the nextChild function, because I can’t see what it called in your code, but you should have something similar or some way to iterate over the children.

An alternative way to save most of your existing code would be to maintain a separate data structure that contains a set of "visited" nodes, it can be as simple as a set of strings, if all your node names are unique - instead of deleting the node, add it into a “visited” set, and in your recursion the condition does not check for null, but rather will find the first invisible node. This is probably more complicated than the one suggested above, but it may be more similar to what you have now - and will avoid loops in the case when you need to do this on a cyclic graph rather than on a tree.

Answer 3

Something that I came up with while working on typing words in TrieTree, which can be easily adapted to other types of trees or different requirements:

 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 great job of managing memory (it uses one HashMap , the size of which will never exceed the height of the tree), and it offers more flexibility (just replace printValues ​​with what you need).

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

Answer 4

1, find the leaf node
2, crawl up 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);