Coding Recipies

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:

/**
  * 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 !!:)

Trees: Iterative Post-order traversal using Single Stack

Problem Statement:
Perform iterative post-order traversal on a binary tree using Single Stack.

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

Solution:
Download Source Code

By post-order traversal I mean , process the Left Node ,then Right Node, and then 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.
Here we are performing iteration using a Single Stack, also refer to my post using two stacks.

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

/**
  * Iterative Pre-order traversal using single stacks
  */
 public void iterativePostOrder(Node root) {
  Stack<Node> stack = new Stack<Node>();
  Node curr = root;
  for (;;) 
  {
   if (curr != null) 
   {
    if (curr.right != null)
     stack.push(curr.right);
    
    stack.push(curr);
    curr = curr.left;
   } 
   else 
   {
    if (!stack.isEmpty())
    {
     curr = stack.pop();
     // odd case, exchange curr and top element
     if (!stack.isEmpty() && curr.right == stack.peek()) 
     {
      stack.pop();
      stack.push(curr);
      curr = curr.right;
     }
     else
     {
      System.out.print(curr+"\t");
      curr=null; //move to right or null
     }

    } else
     break;
   }
  }
 }

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

Trees: Iterative Post-order traversal using two stacks

Problem Statement:
Perform post-order traversal using two stacks for the given binary tree.

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

Solution:
Download Source Code

By post-order traversal I mean , process the Left Node ,then Right Node, and then 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.
Here we are performing iteration using two Stacks, also refer to my post using single stack.

Below is the implementation:

/**
  * Iterative Pre-order traversal using two stacks 
  */
 public void iterativePostOrder(Node root)
 {
   Stack<Node> processed = new Stack<Node>();
   Stack<Node> current = new Stack<Node>();
   
   current.push(root);
   while(!current.isEmpty())
   {
    Node item = current.pop();
    processed.push(item);
    
    if(item.left!=null)
    current.push(item.left);
    if(item.right!=null)
    current.push(item.right);
    
   }
   while(!processed.isEmpty())
   {
    System.out.print(processed.pop() + "\t");
   }
 }

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

13 Apr 2014

Trees: Iterative Inorder Traversal

Trees: Iterative Post-order traversal using Single Stack

Trees: Iterative Post-order traversal using two stacks