Trees: Iterative Pre-order traversal

Problem Statement:
       Perform iterative pre-order traversal using Stack on the given binary tree.

Output: 
Pre-order :  1 , 2 , 4 , 8 , 5 , 3 , 6 , 7 , 9

Solution:
Download Source Code

By pre-order traversal I mean , process the Node, then Left 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
In-order 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
Morris Traversal

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

 Algorithm Involved:   
 1. Push root to stack  
 2. while stack is not empty  
    a. pop from stack, and print  
    b. if left child is not null , push to stack  
    c. If right child is not null , push to stack  
 3.End  

Implementation:

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

/** * Iterative Preorder Traversal Using Stack * @param root: root of tree */ public void iterativePreorder(Node root) { Stack<Node> stack = new Stack<Node>(); if(root!=null) stack.push(root); while(!stack.isEmpty()) { Node item = stack.pop(); System.out.print(item + "\t"); if(item.right!=null) stack.push(item.right); if(item.left!=null) stack.push(item.left); } }

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