Print root to leaf paths without using recursion - GeeksforGeeks
Given a binary tree, print all its root to leaf paths without using recursion. For example, consider the following Binary Tree.
https://www.quora.com/How-do-I-print-all-root-to-leaf-paths-in-binary-tree-iteratively
Read full article from Print root to leaf paths without using recursion - GeeksforGeeks
Given a binary tree, print all its root to leaf paths without using recursion. For example, consider the following Binary Tree.
6
/ \
3 5
/ \ \
2 5 4
/ \
7 4
There are 4 leaves, hence 4 root to leaf paths -
6->3->2
6->3->5->7
6->3->5->4
6->5>4
how to extend the traversal to print root to leaf paths? The idea is to maintain a map to store parent pointers of binary tree nodes. Now whenever we encounter a leaf node while doing iterative preorder traversal, we can easily print root to leaf path using parent pointer/* Function to print root to leaf path for a leaf using parent nodes stored in map */void printTopToBottomPath(Node* curr, map<Node*, Node*> parent){ stack<Node*> stk; // start from leaf node and keep on pushing // nodes into stack till root node is reached while (curr) { stk.push(curr); curr = parent[curr]; } // Start popping nodes from stack and print them while (!stk.empty()) { curr = stk.top(); stk.pop(); cout << curr->data << " "; } cout << endl;}/* An iterative function to do preorder traversal of binary tree and print root to leaf path without using recursion */void printRootToLeaf(Node* root){ // Corner Case if (root == NULL) return; // Create an empty stack and push root to it stack<Node*> nodeStack; nodeStack.push(root); // Create a map to store parent pointers of binary // tree nodes map<Node*, Node*> parent; // parent of root is NULL parent[root] = NULL; /* Pop all items one by one. Do following for every popped item a) push its right child and set its parent pointer b) push its left child and set its parent pointer Note that right child is pushed first so that left is processed first */ while (!nodeStack.empty()) { // Pop the top item from stack Node* current = nodeStack.top(); nodeStack.pop(); // If leaf node encountered, print Top To // Bottom path if (!(current->left) && !(current->right)) printTopToBottomPath(current, parent); // Push right & left children of the popped node // to stack. Also set their parent pointer in // the map if (current->right) { parent[current->right] = current; nodeStack.push(current->right); } if (current->left) { parent[current->left] = current; nodeStack.push(current->left); } }}https://www.quora.com/How-do-I-print-all-root-to-leaf-paths-in-binary-tree-iteratively
Read full article from Print root to leaf paths without using recursion - GeeksforGeeks
