Skip to main content

Inorder traversal of binary tree using stack in java

Java program for Inorder traversal of binary tree using stack. Here problem description and explanation.

// Java program for
// Inorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    // Make a tree node
    public TreeNode(int data)
    {
        // Set node data
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class StackNode
{
    public TreeNode element;
    public StackNode next;
    public StackNode(TreeNode element)
    {
        this.element = element;
        this.next = null;
    }
}
// Stack Class
class MyStack
{
    public StackNode top;
    public int size;
    public MyStack()
    {
        this.top = null;
        this.size = 0;
    }
    // Add new element into stack
    public void push(TreeNode element)
    {
        // Create new node
        StackNode node = new StackNode(element);
        node.next = this.top;
        // new node is new top
        this.top = node;
        // Increase the size
        this.size += 1;
    }
    // Remove top element of the stack
    public void pop()
    {
        if (this.top != null)
        {
            // next node is new top
            this.top = this.top.next;
            // Reduce size
            this.size -= 1;
        }
    }
    // Returns the status of empty or non empty stacks
    public boolean isEmpty()
    {
        if (this.size > 0 && this.top != null)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Return top element of stack
    public TreeNode peek()
    {
        if (isEmpty())
        {
            return null;
        }
        return this.top.element;
    }
}
public class BinaryTree
{
    public TreeNode root;
    public BinaryTree()
    {
        // Set initial tree root to null
        this.root = null;
    }
    // Display Inorder view of binary tree
    public void inorder()
    {
        if (this.root != null)
        {
            // Make new stack 
            MyStack s = new MyStack();
            TreeNode node = this.root;
            // Display tree element
            while (!s.isEmpty() || node != null)
            {
                if (node != null)
                {
                    // Add current node
                    s.push(node);
                    // Visit to left subtree
                    node = node.left;
                }
                else
                {
                    // When node is null
                    // Get stack top element
                    node = s.peek();
                    // Display node value
                    System.out.print(" " + node.data);
                    // Remove top element of the stack
                    s.pop();
                    // Visit to left subtree of current node
                    node = node.right;
                }
            }
        }
        else
        {
            System.out.print("Empty Linked List\n");
        }
    }
    public static void main(String[] args)
    {
        // Create new tree 
        BinaryTree tree = new BinaryTree();
        /*   
            Construct Binary Tree
            -----------------------
                15
               /  \
              24   54
             /    /  \
            35   62   13
         */
        // Add tree nodes
        tree.root = new TreeNode(15);
        tree.root.left = new TreeNode(24);
        tree.root.right = new TreeNode(54);
        tree.root.right.right = new TreeNode(13);
        tree.root.right.left = new TreeNode(62);
        tree.root.left.left = new TreeNode(35);
        // Display result
        tree.inorder();
    }
}

Output

 35 24 15 62 54 13




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment