Inorder Tree Traversal (DFS) in java

# Inorder Tree Traversal (DFS) in java

In our previous post we had discussed about different approaches of implementing Preorder tree traversal. In this article we shall discuss steps and different ways of implementing Inorder tree traversal.

There are different ways to traversal a tree in DFS such as:

1. Preorder
2. Inorder
3. Postorder

Here in this article, we shall discuss steps and different approach of implementing Inorder tree traversal.

### Steps for Inorder Tree Traversal are :

1) Traverse the left subtree, i.e., call Inorder(left-subtree)
2) Visit the root.
3) Traverse the right subtree, i.e., call Inorder(right-subtree)

Inorder Traversal of above tree is 70, 40, 20, 50, 10, 30, 60

Time Complexity: O(n)

1) Recursive
2) Iterative

### Recursive solution for Inorder Tree Traversal :

Recursive solution for Inorder Traversal is similar to the steps we had discussed above. Algorithm for recursive solution is

```1) Traversal left node i.e inorder(root.left)
2) Print root node
3) Traversal right node i.e inorder(root.right)
```

Code for recursive solution

```package com.code2succeed.tree;

public class InorderTraversal {
public static class Node {
private int data;
private Node left;
private Node right;

public Node(int data) {
this.data = data;
}
}

public void inorder(Node root) {
if(root != null) {
//Traversal left subtree
inorder(root.left);
//print root
System.out.println(root.data);
//Traversal right subtree
inorder(root.right);
}
}

public static void main(String[] args) {
Node root = new Node(10);
Node node20 = new Node(20);
Node node30 = new Node(30);
Node node40 = new Node(40);
Node node50 = new Node(50);
Node node60 = new Node(60);
Node node70 = new Node(70);

root.left = node20;
root.right = node30;
node20.left = node40;
node20.right = node50;
node40.left = node70;
node30.right = node60;

InorderTraversal it = new InorderTraversal();
System.out.println("Inorder Traversal - recursive solution : ");
it.inorder(root);
}
}
```

Output

```Inorder Traversal - recursive solution :
70 40 20 50 10 30 60```

### Iterative solution for Inorder Traversal

To implement iterative solution for Inorder Traversal, we will be using Stack data structure. Algorithm for iterative solution is

```1) create stack and initialize currentNode as root.
2) while stack is not empty or currentNode not equals to Null, do the following
- if currentNode != Null, push currentNode to stack and assign currentNode = currentNode.left
- else pop top node from stack, print node data and assign currentNode = stack[top].right
```

Code for iterative solution

```package com.code2succeed.tree;

import java.util.Stack;

public class InorderTraversal {
public static class Node {
private int data;
private Node left;
private Node right;

public Node(int data) {
this.data = data;
}
}

public void inorderIterative(Node root) {
if(root == null) { return; }
Stack<Node> stack = new Stack<Node>();
Node currentNode = root;

while(!stack.isEmpty() || currentNode != null) {
if(currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.left;
}else {
Node top = stack.pop();
System.out.print(top.data+" ");
currentNode = top.right;
}
}
}

public static void main(String[] args) {
Node root = new Node(10);
Node node20 = new Node(20);
Node node30 = new Node(30);
Node node40 = new Node(40);
Node node50 = new Node(50);
Node node60 = new Node(60);
Node node70 = new Node(70);

root.left = node20;
root.right = node30;
node20.left = node40;
node20.right = node50;
node40.left = node70;
node30.right = node60;

InorderTraversal it = new InorderTraversal();
System.out.println("\nInorder Traversal - iterative solution : ");
it.inorderIterative(root);
}
}
```

Output

```Inorder Traversal - iterative solution :
70 40 20 50 10 30 60```