Trees: Iterative Inorder Traversal

Problem Statement:
       Perform In-order traversal of the given  binary tree using stack.

Output: 
In-order :  6 , 7 , 8 , 10 , 12 , 14 , 16 , 18 , 20

Solution:
Download Source Code

By in-order traversal I mean , process the Left Node , then Node , and then Right Node, all this processing happens in Depth First Search fashion. I assume that you know the recursive way to iterate a binary tree.

Pre-order Traversal : Node, Left Node, Right Node   -  +AB
Inorder Traversal : Left Node, Node , Right Node      -  A+B
Post-order Traversal: Left Node, Right Node, Node   -  AB+

Iterative Traversal can also be done by Morris traversal , which uses the concept of Threaded Binary Trees

Below is the algorithm and implementation of in-order traversal using Stack.

 Algorithm Involved:   
 1. root!=null  
 2. current = root   
 3. for(;;)  
 A. If current is not null   
     a. push to stack  
     b. move current to left  
 B. If current is null and stack is not empty  
     a. pop from stack  
     b. print poped item  
     c. puch poped items right child if not null  
 C. If stack is empty , END  

Implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

/** * Iterative Inorder Traversal using Stack * @param node */ public void iterativeInorder(Node node) { Stack<Node> stack = new Stack<Node>(); for (;;) { if (node != null) { stack.push(node); node = node.left; } else { if (!stack.isEmpty()) { node = stack.pop(); System.out.print(node + "\t"); node = node.right; } else break; } } }

Please post your suggestion and comments.
Happy Coding !!:)