Given the root of a binary tree, return the Inorder traversal of its nodes’ values.

1. Introduction

In this article, I will discuss how to traverse a Binary Tree using Inorder traversal(Inorder traversal algorithm) using Recursive and Iterative(without recursion) methods.

This article is part of Binary Tree-Traversals. Read more about Binary Tree traversals here.

2. Content

Below are 3 examples of Binary Tree and their respective Inorder traversal results.

Example 1:

Inorder Traversal = [4,2,5,1,6,3,7]

Example 2:

Inorder Traversal = [4,10,2,1,5,7,3,8,6]

Example 3:

Inorder Traversal = [2,5,7,10,12,15,17]

3. Inorder Traversal

Steps for Inorder traversal:

1. Recursively traverse the current node’s left sub-tree
2. If no left sub-tree exists, then visit the node
3. Recursively traverse the current node’s right sub-tree

The good part about recursion is that we don’t need to track the nodes in the stack. The system stack takes care of that for us. This makes our job really easy if we are implementing the traversal using recursion.

4. Inorder Traversal using Recursion

In order to save the result of traversal, we need to use ArrayList.

Below is the code for Inorder Traversal of Binary Tree using Recursion.

public List<Integer> inorder(TreeNode root) {
   List<Integer> result = new ArrayList<>();
   inorder(root, result);
   return Collections.unmodifiableList(result);
}

private void inorder(TreeNode root, List<Integer> result) {
   if(root != null) {
       inorder(root.left, result);
       result.add(root.val);
       inorder(root.right, result);
   }
}

Time Complexity: 

1. O(n) where n is the total number of nodes in the Binary Tree.

Space Complexity:

1. O(h) where h is the height of the tree. If the tree is skewed, then the factor h degrades to n, where n is the total number of nodes in the tree. Below is what a skewed tree looks like.

5. Inorder Traversal using Iteration

In Order to write code using an iterative way, we need to use a Stack data structure to save the elements that we are traversing. In Recursion we use system stack but in Iteration we need to use external Stack to traverse Binary Tree using Inorder traversal.

Below is the code to traverse a Binary Tree using Inorder Traversal.

public List<Integer> inorder(TreeNode root) {
   TreeNode curr = root;
   List<Integer> result = new ArrayList<>();
   Deque<TreeNode> stack = new ArrayDeque<>();

   while (curr != null || !stack.isEmpty()) {
       while (curr != null) {
           // Push the left subtree in the stack.
           stack.push(curr);
           curr = curr.left;
       }
       // Visit the node as no left subtree exists.
       curr = stack.pop();
       result.add(curr.val);
       // Visit the right subtree
       curr = curr.right;
   }
   return Collections.unmodifiableList(result);
}

Time Complexity:

1. O(n) where n is the total number of nodes in the Binary Tree.

Space Complexity:

1. O(h) where h is the height of the tree. If the tree is skewed, then the factor h degrades to n, where n is the total number of nodes in the tree.

5. Conclusion

In this article, we saw Inorder Traversal of the Binary Tree using Recursion and Iteration.

Github Link: https://github.com/savanibharat/justamonad-tutorials/blob/master/justamonad-tutorials-leetcode/src/main/java/com/justamonad/tutorials/leetcode/tree/InorderTraversal.java