Print root to leaf paths without using recursion | Java 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 program to test above functions ; Constructed binary tree is 10 / \ 8 2 / \ / 3 5 2
import java . util . Stack ; import java . util . HashMap ; public class PrintPath { class Node { int data ; Node left , right ; Node ( int data ) { left = right = null ; this . data = data ; } } ; public static void printTopToBottomPath ( Node curr , HashMap < Node , Node > parent ) { Stack < Node > stk = new Stack < > ( ) ; while ( curr != null ) { stk . push ( curr ) ; curr = parent . get ( curr ) ; } while ( ! stk . isEmpty ( ) ) { curr = stk . pop ( ) ; System . out . print ( curr . data + " ▁ " ) ; } System . out . println ( ) ; } public static void printRootToLeaf ( Node root ) { if ( root == null ) return ; Stack < Node > nodeStack = new Stack < > ( ) ; nodeStack . push ( root ) ; HashMap < Node , Node > parent = new HashMap < > ( ) ; parent . put ( root , null ) ; while ( ! nodeStack . isEmpty ( ) ) { Node current = nodeStack . pop ( ) ; if ( current . left == null && current . right == null ) printTopToBottomPath ( current , parent ) ; if ( current . right != null ) { parent . put ( current . right , current ) ; nodeStack . push ( current . right ) ; } if ( current . left != null ) { parent . put ( 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 ) ; } }