Print each path of a leaf of a tree without recursive

Question

How to print each path to a tree without using recursion.

This is a tree, not a binary tree.

struct node { int data std::vector<node*> children; } 

Print all the way from root to leaf, i.e. next tree

• r: this is root root
• d, m, n - r children
• x, y, z - child elements
• for m there is no child
• o, p - n children

  ------------- root
 ------ dmn
 --- xyzop

The result should be:

  root-dx
 root-dy
 root-dz
 root-m
 root-no
 root-np

I tried using a non-recursive path, but could not.

Answer 1

 public static void printAllPathToLeafNonRecursive(Node root) { if (root == null) { return; } Queue<Object> q = new LinkedList<Object>(); q.add(root); q.add(root.data + ""); while(!q.isEmpty()){ Node head = (Node) q.poll(); String headPath = (String) q.poll(); if(head.isLeaf()){ System.out.println(headPath); continue; } if(head.left!=null){ String leftStr = headPath + "->" + head.left.data; q.add(head.left); q.add(leftStr); } if(head.right!=null){ String rightStr = headPath + "->" + head.right.data; q.add(head.right); q.add(rightStr); } } } 

Answer 2

Here, the Python-based solution relies solely on a preliminary iterative stack traversal. Prints both paths and paths.

  class Stack(object): # just for reference def __init__(self): self.a = [] def push(self, b): self.a.append(b) def peek(self): return self.a[-1] def pop(self): return self.a.pop() def isEmpty(self): return len(self.a) == 0 def show(self): return self.a def paths(troot): # you should create your own Tree and supply the root current = troot s = Stack() s.push(current) s.push(str(current.key)) s.push(current.key) while not s.isEmpty(): pathsum = s.pop() path = s.pop() current = s.pop() if not current.left and not current.right: print 'path: %s, pathsum: %d' % (path, pathsum) if current.right: rightstr = path + "->" + str(current.right.key) rightpathsum = pathsum * 10 + current.right.key s.push(current.right) s.push(rightstr) s.push(rightpathsum) if current.left: leftstr = path + "->" + str(current.left.key) leftpathsum = pathsum * 10 + current.left.key s.push(current.left) s.push(leftstr) s.push(leftpathsum) 

For example, for the following tree:

  3 / \ / \ / \ / \ / \ / \ / \ / \ 1 7 / \ / \ / \ / \ / \ / \ / \ / \ 0 2 5 8 / \ / \ / \ / \ / \ / \ / \ / \ NUL NUL NUL NUL 4 6 NUL 9 

The conclusion will be:

  >>> paths() path: 3->1->0, pathsum: 310 path: 3->1->2, pathsum: 312 path: 3->7->5->4, pathsum: 3754 path: 3->7->5->6, pathsum: 3756 path: 3->7->8->9, pathsum: 3789 

Answer 3

The strategy is simple. Go down, straight, then up. At each point, you know where to go next.

Save the vector, which is your current place in the tree. Start it from the root. And then in the pseudo code:

 while True: if not a leaf: current_place.push_back(0) // move down one else: print current path. while can't move right: if at root: exit() current_place.pop_back() //move up one current_place[-1] += 1 

These operations will require function calls. But they are function calls with loops, not recursion, so they are not recursive.

Answer 4

In the end, it's just a schedule. There are different types of graph traversals. Just use dfs with the stack and print the nodes from which you don't have front edges.

Answer 5

 public static void RoottoPathPrint(BinaryTreeNode root) { Stack<Object> stack = new Stack<Object>(); if (root == null) return; stack.push(root.getData() + ""); stack.push(root); while (!stack.isEmpty()) { BinaryTreeNode temp = (BinaryTreeNode) stack.pop(); String path = (String) stack.pop(); if (temp.getRight() != null) { stack.push(path + temp.getRight().getData()); stack.push(temp.getRight()); } if (temp.getLeft() != null) { stack.push(path + temp.getLeft().getData()); stack.push(temp.getLeft()); } if (temp.getLeft() == null && temp.getRight() == null) { System.out.println(path); } } } 

The idea is to track both the path and the nodes on the same stack as we cross the tree. The stack of this object will take care of this. Hope this helps!

Answer 6

 private void rootToLeaf(BSTNode root){ Stack<Map<BSTNode,ArrayList<Integer>>> tmpStack = new Stack<Map<BSTNode,ArrayList<Integer>>>(); Map<BSTNode,ArrayList<Integer>> tmpMap = new HashMap<BSTNode,ArrayList<Integer>>(); //List<Integer> tmp_arraylist = new ArrayList<Integer>(); ArrayList<Integer> tmpList = new ArrayList<Integer>(); tmpList.add(root.data); tmpMap.put(root, tmpList); tmpStack.push(tmpMap); while(!tmpStack.isEmpty()){ Map<BSTNode,ArrayList<Integer>> temp_map = tmpStack.pop(); for(BSTNode node : temp_map.keySet()){ if(node.getLeft()==null && node.getRight()==null){ for(int i: temp_map.get(node)){ System.out.print(i+" "); } System.out.println(); } if(node.getRight()!=null){ ArrayList<Integer> tmp_List = new ArrayList<Integer>(); for(int i: temp_map.get(node)){ tmp_List.add(i); } tmp_List.add(node.getRight().getData()); Map<BSTNode,ArrayList<Integer>> tmphashMap = new HashMap<BSTNode,ArrayList<Integer>>(); tmphashMap.put(node.getRight(), tmp_List); tmpStack.push(tmphashMap); } if(node.getLeft()!=null){ ArrayList<Integer> tmp_List = new ArrayList<Integer>(); for(int i: temp_map.get(node)){ tmp_List.add(i); } tmp_List.add(node.getLeft().getData()); Map<BSTNode,ArrayList<Integer>> tmphashMap = new HashMap<BSTNode,ArrayList<Integer>>(); tmphashMap.put(node.getLeft(), tmp_List); tmpStack.push(tmphashMap); } } } } 

Answer 7

For n-ary tree - the path of DFS and BFS, the sum

  100 / / \ \ 1 2 3 4 / / / / / / \ 10 11 12 13 14 40 41 / \ 400 401 public void traverseDFS(Node root) { Stack<Node> s = new Stack<Node>(); Stack<String> sPath = new Stack<>(); Stack<Integer> sSum = new Stack<>(); s.push(root); sPath.push(root.Id + ""); sSum.push(root.Id); while (!s.isEmpty()) { // Pop out Node head = s.pop(); String headPath = sPath.pop(); Integer headSum = sSum.pop(); if(head.children == null || head.children.isEmpty()){ //Leaf System.out.println(headPath + "(" + headSum+")"); continue; } for(Node child : head.children) { String path = headPath + "->" + child.Id; Integer sum = headSum + child.Id; // Push on stack s.push(child); sPath.push(path); sSum.push(sum); } } } public static void traverseBFS(Node root) { Queue<Node> q = new LinkedList<>(); Queue<String> qPath = new LinkedList<>(); Queue<Integer> qSum = new LinkedList<>(); q.add(root); qPath.add(root.Id + ""); qSum.add(root.Id); while(!q.isEmpty()){ // Poll the q Node head = q.poll(); String headPath = qPath.poll(); Integer headSum = qSum.poll(); if(head.children == null || head.children.isEmpty()){ //Leaf System.out.println(headPath + "(" + headSum+")"); continue; } for(Node child : head.children) { String path = headPath + "->" + child.Id; Integer sum = headSum + child.Id; // Add to the q q.add(child); qPath.add(path); qSum.add(sum); } } } class Node { int Id; String Data; Node Parent; ArrayList<Node> children; public Node(int id, String data) { Id = id; Data = data; } } 

Exit

 -----------Depth FS------------- 100->4->41(145) 100->4->40->401(545) 100->4->40->400(544) 100->3(103) 100->2(102) 100->1->14(115) 100->1->13(114) 100->1->12(113) 100->1->11(112) 100->1->10(111) -----------BFS------------- 100->2(102) 100->3(103) 100->1->10(111) 100->1->11(112) 100->1->12(113) 100->1->13(114) 100->1->14(115) 100->4->41(145) 100->4->40->400(544) 100->4->40->401(545)