Question : Binary Tree InOrder traversal in java

 InOrder traversal:

In InOrder traversal, each node is processed between subtrees. In simpler words, Visit the left subtree, node, and then right subtree.

Steps for InOrder traversal are:

• Traverse the left subtree in InOrder.
• Visit the node.
• Traverse the right subtree in InOrder

There can be two ways of implementing it

• Recursive
• Iterative

Recursive solution

The recursive solution is very straightforward. The below diagram will make you understand recursion better.

Code for recursion will be::

 
// Recursive Solution
    public void inOrder(TreeNode root) {
        if(root !=  null) {
            inOrder(root.left);
            //Visit the node by Printing the node data
            System.out.printf("%d ",root.data);
            inOrder(root.right);
        }
    }

Iterative solution

For recursion, we use an implicit stack. So here to convert the recursive solution to iterative, we will use the explicit stack.
Steps for iterative solution:

1. Create an empty stack s and Initialize currentNode as root
2. Push the currentNode to s and set currentNode = currentNode.left until currentNode is NULL
3. If currentNode is NULL and s is not empty then
   • Pop the top node from stack s and print it
   •  set currentNode = currentNode.right
   • go to step 2
4. If stack is empty and currentNode is also null then we are done with it

// Iterative solution
    public void inOrderIter(TreeNode root) {
 
        if(root == null)
            return;
 
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode currentNode=root;
 
        while(!s.empty() || currentNode!=null){
 
            if(currentNode!=null)
            {
                s.push(currentNode);
                currentNode=currentNode.left;
            }
            else
            {
                TreeNode n=s.pop();
                System.out.printf("%d ",n.data);
                currentNode=n.right;
            }
        }
    }

Let's create java program for InOrder traversal::

import java.util.Stack;
 
public class BinaryTreeInOrder {
 
    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }
 
    // Recursive Solution
    public void inOrder(TreeNode root) {
        if(root !=  null) {
            inOrder(root.left);
            //Visit the node by Printing the node data
            System.out.printf("%d ",root.data);
            inOrder(root.right);
        }
    }
 
    // Iterative solution
    public void inOrderIter(TreeNode root) {
 
        if(root == null)
            return;
 
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode currentNode=root;
 
        while(!s.empty() || currentNode!=null){
 
            if(currentNode!=null)
            {
                s.push(currentNode);
                currentNode=currentNode.left;
            }
            else
            {
                TreeNode n=s.pop();
                System.out.printf("%d ",n.data);
                currentNode=n.right;
            }
        }
    }
 
    public static void main(String[] args)
    {
        BinaryTreeInOrder bi=new BinaryTreeInOrder();
        // Creating a binary tree
        TreeNode rootNode=createBinaryTree();
        System.out.println("Using Recursive solution:");
 
        bi.inOrder(rootNode);
 
        System.out.println();
        System.out.println("-------------------------");
        System.out.println("Using Iterative solution:");
 
        bi.inOrderIter(rootNode);
    }
 
    public static TreeNode createBinaryTree()
    {
 
        TreeNode rootNode =new TreeNode(40);
        TreeNode node20=new TreeNode(20);
        TreeNode node10=new TreeNode(10);
        TreeNode node30=new TreeNode(30);
        TreeNode node60=new TreeNode(60);
        TreeNode node50=new TreeNode(50);
        TreeNode node70=new TreeNode(70);
 
        rootNode.left=node20;
        rootNode.right=node60;
 
        node20.left=node10;
        node20.right=node30;
 
        node60.left=node50;
        node60.right=node70;
 
        return rootNode;
    }
}

Run the above program and you will get the following output::

Using Recursive solution:
10 20 30 40 50 60 70
————————-
Using Iterative solution:
10 20 30 40 50 60 70

Don't miss the next article! 
Be the first to be notified when a new article or Kubernetes experiment is published.                            

 

 Share This

• Facebook

• Twitter

• Linkedin

• Pinterest