Depth-First Search - Inorder Traversal of a Binary Tree

Intro

In the previous post, we covered the Preorder traversal of a Binary Tree, and here, we'll go through one more DFS strategy of a tree traversal: Inorder Traversal. It is similar to the Preorder, just the order in which we visit the nodes is a bit different.

Inorder Traversal - How does it work?

In the Inorder traversal, we first handle/print the left child, then the root, and then the right child. So the order is: Left, Root, Right.

Let's say we have the following tree structure:

During the Inorder traversal, we handle/print the elements in the following order: Left, Root, and Right.
So the output should be 4, 2, 5, 1, 6, 3, 7.

Inorder Traversal implementation

We can implement the algorithm in two ways: recursive and iterative.

First, let's create a Tree class and a Node class:

class Node {
  Node left;
  Node right;
  int value;

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


class Tree {

  Node root;

}

Recursive Inorder

Below is the implementation of the recursive method inorder:

public void inorder(Node root) {

  if (root == null) { // BASE CASE
    return;
  }

  inorder(root.left);
  System.out.println(root.value);
  inorder(root.right);

}

Here, inside the recursive method inorder, we first have a base case, where we check if the root is null. If the result is true, we exit the method.

If not, we recursively call the method providing the left child, then we print the root, and we call again the inorder method passing the right child as an argument.

In recursion, the most important part is the stack of the method calls. 

To understand how this recursive inorder method works, we need to keep track of the internal stack that gets created when we start calling the inorder method recursively.

Have a look at the Preorder traversal post, where we have gone through every step of the recursion method calls and we kept track of everything that is going on, including the current root element and the program lines.

Use the same approach to keep track of the recursion process here, to better grasp what is going on under the hood as we execute the method inorder recursively.

Iterative Inorder

Here, since we can not rely on the method call stack, like in recursion, we need to find other ways to keep track of the nodes that we visited so that we can go back to them when needed.

Stack data structure to the rescue! 

We can implement and use our own Stack data structure. The stack is a LIFO data structure, which means the element we last added will be the first one that popped out of the stack.

Let's see the iterative implementation of the inorder method:

public void inorder() {
  if (root == null) {
    return;
  }

  Stack<Node> stack = new Stack<>();
  Node temp = root;

  while (!stack.isEmpty() || temp != null) {
    if (temp != null) {
      stack.push(temp);
      temp = temp.left;
    } else {
      temp = stack.pop();
      System.out.println(temp.value);
      temp = temp.right;
    }
  }
}

Here, we create a new stack and assign the root to the temp variable.

We introduced a while loop that will iterate as long the stack is not empty OR the temp is not null. 

When the stack becomes empty and the temp becomes null, the while loop will end.

The rest of the logic is as follows:

If the temp is not null, we will push it to the stack and set the new temp to the left child of the current temp. The next iteration begins. We will be pushing all the left nodes until we get to the end. In that case, the temp will be null and on the next iteration, we will pop the element that we added last, and print it. Then, we are setting the right child as a new temp, because we know that we already traverse the left side nodes.

The whole flow is like this:
In the first three iterations, the temp will not be null and we will be adding nodes to the stack in this order: 1, 2, 4 - (all the nodes on the left side of the tree). So we will be setting the temp to the temp.left in all three iterations. Now on the fourth iteration, the temp is null, since we got to the leaf node (number 4) and we set temp to temp.left - which is null.

Now is the point where we pop the element and print it. We popped the last element that we added, which is 4 and we printed it. (queue now has only these elements: [1,2]).
Now we set temp to the right child of the number 4. It is also null, so we pop the next element, the first element from behind in the queue, and that is number 2. (queue = [1]). So we now print number 2 and set the new temp to temp.right - which is number 5. 

In the next iteration, the temp is not null (it is 5), and we push the 5 to the queue and set the temp to the left child of the number 5. (queue = [1,5]). 

The temp is now null and we pop the element 5 from the queue since we added it last. (queue = [1]). We print the element number 5 and set the temp to the right child, which is null.

Now we see that temp is null and we pop the number 1 which was the only element inside the queue and we print it.

Current printed elements are 4, 2, 5, 1.

Now we set temp to be the right child of the node with number 1, which is the node with number 3.

In the next iteration, the temp is not null, so we add the node with value 3 to the queue and the queue has one element - [3]. We set temp to be temp.left - which is the node with a value of 6.

In the next iteration, we see that the temp is not null and we push it to the queue. (queue = [3, 6]). 
We set the new temp to the left child of the current temp and it has the value of null.
So in the next iteration, we see that temp is null, so we pop the last node added (number 6) and print it. We set the temp to the right child of the temp. And it is also null.

Now, in the while loop, we see that temp is null and we pop the last added element - which is number 3 and print it. We set the new temp to the right child of the current temp - which is a node with a value of 7.

In the next iteration, we push the 7 to the queue and set the temp to the left child - which is null.

Now, in the next iteration, since the temp is null, we pop the node with value 7 and print it, and se the temp to the temp.right.

In the last iteration, the stack is empty and the temp is null so we finish with the execution since we traversed through the entire tree.

The elements were printed in the following order: 4, 2, 5, 1, 6, 3, 7.

And that's it.

The important thing here is that we need to keep track of elements that we are adding to the queue so that we know which element will be popped next.
I advise drawing on the white table or using paper and pen for this.

Inorder traversal - analysis

The time complexity of the Inorder traversal is O(n) since we need to visit every node in the tree.

Space complexity is O(1) for recursive - unless we want to count the stack that is being created in the background - then it is O(n).

For the iterative way - space complexity is O(n) since we are creating a Stack data structure that requires additional space in memory. 

The size of the stack is proportional to the number of nodes inside the tree.