## Sunday, May 8, 2016

### Print root to leaf paths without using recursion - GeeksforGeeks

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