Print root to leaf paths without using recursion | C ++ program to Print root to leaf path WITHOUT using recursion ; A binary tree ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; Function to print root to leaf path for a leaf using parent nodes stored in map ; start from leaf node and keep on pushing nodes into stack till root node is reached ; Start popping nodes from stack and print them ; An iterative function to do preorder traversal of binary tree and print root to leaf path without using recursion ; Corner Case ; Create an empty stack and push root to it ; Create a map to store parent pointers of binary tree nodes ; parent of root is 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 ; Pop the top item from stack ; If leaf node encountered , print Top To Bottom path ; Push right & left children of the popped node to stack . Also set their parent pointer in the map ; Driver program to test above functions ; Constructed binary tree is 10 / \ 8 2 / \ / 3 5 2
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; Node * newNode ( int data ) { Node * node = new Node ; node -> data = data ; node -> left = node -> right = NULL ; return node ; } void printTopToBottomPath ( Node * curr , map < Node * , Node * > parent ) { stack < Node * > stk ; while ( curr ) { stk . push ( curr ) ; curr = parent [ curr ] ; } while ( ! stk . empty ( ) ) { curr = stk . top ( ) ; stk . pop ( ) ; cout << curr -> data << " ▁ " ; } cout << endl ; } void printRootToLeaf ( Node * root ) { if ( root == NULL ) return ; stack < Node * > nodeStack ; nodeStack . push ( root ) ; map < Node * , Node * > parent ; parent [ root ] = NULL ; while ( ! nodeStack . empty ( ) ) { Node * current = nodeStack . top ( ) ; nodeStack . pop ( ) ; if ( ! ( current -> left ) && ! ( current -> right ) ) printTopToBottomPath ( current , parent ) ; if ( current -> right ) { parent [ current -> right ] = current ; nodeStack . push ( current -> right ) ; } if ( current -> left ) { parent [ current -> left ] = current ; nodeStack . push ( current -> left ) ; } } } int main ( ) { Node * root = newNode ( 10 ) ; root -> left = newNode ( 8 ) ; root -> right = newNode ( 2 ) ; root -> left -> left = newNode ( 3 ) ; root -> left -> right = newNode ( 5 ) ; root -> right -> left = newNode ( 2 ) ; printRootToLeaf ( root ) ; return 0 ; }