Binary Tree Inorder Traversal | Leetcode #94 | Medium

In this post I will discuss the solution to the leetcode problem — Binary Tree Inorder Traversal.

Problem:

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [2,1]

Example 5:

Input: root = [1,null,2]
Output: [1,2]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Follow up:

Recursive solution is trivial, could you do it iteratively?

Solution:

Trees are not linear data structures like arrays, lists etc. and hence they can be traversed in multiple ways. In-order traversal is a way of traversal where we visit the tree nodes in this order — left, root, right.

As the problem statement mentions, the recursive solution is trivial and asks to solve it in iterative way. Let’s solve them in both the ways.

1. Recursive Solution:

The structure of TreeNode is mentioned in the comments where it has val holding the value and left and right which are corresponding left and right child nodes.

Here is how the recursive algorithm looks like —

1. Create a List<Integer> and let’s call it output which will hold the result of in-order traversal.
2. Create a helper function traverse() which we can call recursively by passing a TreeNode .
3. Start by calling the traverse() function with root as the input.
4. As every recursive function needs a base condition so that the execution stops, in this case we check if the passed root is null or not. If it is, then we return an empty list.
5. Otherwise, call the traverse() function with root.left which will traverse the left subtree recursively.
6. Add root.val to the output which means we have visited the current node.
7. Call the traverse() function with root.right which will traverse the right subtree recursively.

That’s it. That traverses the entire tree in in-order way. Here is how the code looks like —

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  
  private List<Integer> output = new ArrayList();
    
  public List<Integer> inorderTraversal(TreeNode root) {    
    return traverse(root);
  }
    
  private List<Integer> traverse(TreeNode root) {
    if (root == null) {
      return new ArrayList();
    }
    
    traverse(root.left);
    output.add(root.val);
    traverse(root.right);
    
    return output;
  }
}

2. Iterative Solution:

To traverse the tree in iterative way, we need to take help of another data structure i.e. Stack. As Stack is a last in first out (LIFO) data structure, it perfectly suits our needs to traverse the tree. Let’s see how —

1. Create a List<Integer> and let’s call it output which will hold the result of in-order traversal.
2. Create a stack for storing the TreeNode and call it stack .
3. Create a temporary TreeNode called current and initialized it with root .
4. Iterate the tree until the current is null OR the stack is empty.
5. As we are traversing in-order, we need to keep traversing left until we reach the leaf nodes i.e. the node does not have any children. We can do that by keep pushing the current nodes to the stack and moving current to the left.
6. Once we are done with step 5, we get the top most node from the stack i.e. stack.pop() which is our new current node.
7. Add it to the output.
8. Now we need to move to the right subtree and hence assign current to the left node.
9. Return the output .

This is how the code looks like —

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> output = new ArrayList();
    
    Stack<TreeNode> stack = new Stack();    
    TreeNode current = root;
        
    while(current != null || !stack.isEmpty()) {
      while(current != null) {
        stack.push(current);
        current = current.left;
      }
      
      current = stack.pop();
      output.add(current.val);
      current = current.right;
    }
    return output;
  }
}

I hope you enjoyed solving this problem and the solution helps! Happy coding! 🙂

If you think the solution can be improved or misses something, feel free to comment. There is always some room for improvement.

Find the solutions to the leetcode problems here — https://github.com/rishikeshdhokare/leetcode-problems