Print root to leaf paths without using recursion | Helper function that allocates a new node with the given data and None 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 appending 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 append root to it ; Create a map to store parent pointers of binary tree nodes ; parent of root is None ; Pop all items one by one . Do following for every popped item a ) append its right child and set its parent pointer b ) append its left child and set its parent pointer Note that right child is appended first so that left is processed first ; Pop the top item from stack ; If leaf node encountered , print Top To Bottom path ; append right & left children of the popped node to stack . Also set their parent pointer in the map ; Driver Code ; Constructed binary tree is 10 / \ 8 2 / \ / 3 5 2
class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def printTopToBottomPath ( curr , parent ) : NEW_LINE INDENT stk = [ ] NEW_LINE while ( curr ) : NEW_LINE INDENT stk . append ( curr ) NEW_LINE curr = parent [ curr ] NEW_LINE DEDENT while len ( stk ) != 0 : NEW_LINE INDENT curr = stk [ - 1 ] NEW_LINE stk . pop ( - 1 ) NEW_LINE print ( curr . data , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT def printRootToLeaf ( root ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return NEW_LINE DEDENT nodeStack = [ ] NEW_LINE nodeStack . append ( root ) NEW_LINE parent = { } NEW_LINE parent [ root ] = None NEW_LINE while len ( nodeStack ) != 0 : NEW_LINE INDENT current = nodeStack [ - 1 ] NEW_LINE nodeStack . pop ( - 1 ) NEW_LINE if ( not ( current . left ) and not ( current . right ) ) : NEW_LINE INDENT printTopToBottomPath ( current , parent ) NEW_LINE DEDENT if ( current . right ) : NEW_LINE INDENT parent [ current . right ] = current NEW_LINE nodeStack . append ( current . right ) NEW_LINE DEDENT if ( current . left ) : NEW_LINE INDENT parent [ current . left ] = current NEW_LINE nodeStack . append ( current . left ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 10 ) NEW_LINE root . left = newNode ( 8 ) NEW_LINE root . right = newNode ( 2 ) NEW_LINE root . left . left = newNode ( 3 ) NEW_LINE root . left . right = newNode ( 5 ) NEW_LINE root . right . left = newNode ( 2 ) NEW_LINE printRootToLeaf ( root ) NEW_LINE DEDENT