## Tuesday, May 3, 2022

### 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.