Wednesday, February 25, 2015

Java code for Iterative Inorder Traversal of a Binary Tree

import java.util.*;
import java.lang.*;
import java.io.*;

class BinaryTreeInorderTraversal
{
    public static Stack stack = new Stack();
    public static void main (String[] args) throws java.lang.Exception
    {
        // create some input
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.right.left = new Node(4);
       
        iterativeInorder(head);
    }
   
    static void iterativeInorder(Node head)
    {
        Node current = head;
        while( current != null )
        {
           
            if( current.left != null && current.left.visited == false)
            {   
                stack.push( current );
                current = current.left;
                continue;
            }
            else
            {
                visit(current);
                current.visited = true;
            }
           
            if( current.right != null )
            {
                current = current.right;
            }
            else
            {
                if( ! stack.empty() )
                {
                    current = (Node) stack.pop();   
                }
                else
                {
                    current = null;
                }
               
            }
           
        }
    }
   
    static void visit(Node current)
    {
        System.out.println(current.value+"\n");
    }
}

class Node
{
    public Node left=null;
    public int value;
    public boolean visited=false;
    public Node right=null;
   
    public Node(int value)
    {
        this.value = value;
    }
}

Test Execute it here.

No comments:

Post a Comment