Print root to leaf paths without using recursion | C # program to Print root to leaf path WITHOUT using recursion ; A binary tree node ; 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 code ; Constructed binary tree is 10 / \ 8 2 / \ / 3 5 2
using System ; using System . Collections . Generic ; public class PrintPath { public class Node { public int data ; public Node left , right ; public Node ( int data ) { left = right = null ; this . data = data ; } } ; public static void printTopToBottomPath ( Node curr , Dictionary < Node , Node > parent ) { Stack < Node > stk = new Stack < Node > ( ) ; while ( curr != null ) { stk . Push ( curr ) ; curr = parent [ curr ] ; } while ( stk . Count != 0 ) { curr = stk . Pop ( ) ; Console . Write ( curr . data + " ▁ " ) ; } Console . WriteLine ( ) ; } public static void printRootToLeaf ( Node root ) { if ( root == null ) return ; Stack < Node > nodeStack = new Stack < Node > ( ) ; nodeStack . Push ( root ) ; Dictionary < Node , Node > parent = new Dictionary < Node , Node > ( ) ; parent . Add ( root , null ) ; while ( nodeStack . Count != 0 ) { Node current = nodeStack . Pop ( ) ; if ( current . left == null && current . right == null ) printTopToBottomPath ( current , parent ) ; if ( current . right != null ) { parent . Add ( current . right , current ) ; nodeStack . Push ( current . right ) ; } if ( current . left != null ) { parent . Add ( current . left , current ) ; nodeStack . Push ( current . left ) ; } } } public static void Main ( String [ ] args ) { Node root = new Node ( 10 ) ; root . left = new Node ( 8 ) ; root . right = new Node ( 2 ) ; root . left . left = new Node ( 3 ) ; root . left . right = new Node ( 5 ) ; root . right . left = new Node ( 2 ) ; printRootToLeaf ( root ) ; } }