Binary Tree Inorder Traversal

Description

Binary Tree Inorder Traversal

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]
Explanation:

Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]
Explanation:

Example 3:
Input: root = []
Output: []

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

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?

Approach - Recursion

class Solution {
    List<Integer> ans = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        dfs(root);
        return ans;
    }
 
    void dfs (TreeNode root) {
        if (root == null) return;
 
        dfs(root.left);
        ans.add(root.val);
        dfs(root.right);
    }
}

Approach 1: Recursive Traversal ($O(N)$ Time, $O(N)$ Space)

Intuition

Traverse the binary tree following the in-order sequence: Left subtree $\to$ Root node $\to$ Right subtree. Recursively visit left nodes until hitting null, add the current node’s value to the result list, and then process the right child.

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }
 
    private void inorder(TreeNode node, List<Integer> result) {
        if (node == null) return;
        inorder(node.left, result);
        result.add(node.val);
        inorder(node.right, result);
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Every node in the binary tree is visited exactly once.
• Space Complexity: $O(N)$ worst-case call stack depth for a skewed tree ($O(\log N)$ for a balanced tree).

---

Approach 2: Iterative Stack ($O(N)$ Time, $O(N)$ Space)

Intuition

Simulate the recursion call stack using an explicit Stack:

1. Push the current node and all of its left descendants onto the stack until reaching null.
2. Pop the top node from the stack, visit it by appending its value to the result list.
3. Move the pointer to its right child and repeat the process until both the current pointer and stack are empty.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
 
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>(); // Standard modern Java Stack
        TreeNode curr = root;
 
        while (curr != null || !stack.isEmpty()) {
            // Push all left children to stack
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
 
            // Process top element
            curr = stack.pop();
            result.add(curr.val);
 
            // Move to right subtree
            curr = curr.right;
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Each node is pushed and popped from the stack at most once.
• Space Complexity: $O(N)$ — Auxiliary space required for the explicit stack.

---

Approach 3: Morris Inorder Traversal (Optimal — $O(N)$ Time, $O(1)$ Space)

Intuition

Traverse without recursion or a stack by modifying tree pointers temporarily:

1. If curr.left is null, record curr.val and step right (curr = curr.right).
2. Otherwise, find the in-order predecessor (rightmost node in the left subtree):
   • If pred.right is null, create a temporary link pred.right = curr and move left (curr = curr.left).
   • If pred.right == curr, restore the tree structure by setting pred.right = null, record curr.val, and move right (curr = curr.right).

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        TreeNode curr = root;
 
        while (curr != null) {
            if (curr.left == null) {
                result.add(curr.val);
                curr = curr.right;
            } else {
                // Find in-order predecessor
                TreeNode pred = curr.left;
                while (pred.right != null && pred.right != curr) {
                    pred = pred.right;
                }
 
                if (pred.right == null) {
                    pred.right = curr; // Create temporary thread back to curr
                    curr = curr.left;
                } else {
                    pred.right = null; // Remove thread and visit curr
                    result.add(curr.val);
                    curr = curr.right;
                }
            }
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Traversing edges and restoring pointers takes at most $2N$ steps in total.
• Space Complexity: $O(1)$ auxiliary space — Tree structure modified temporarily without extra data structures.

---

Easy Memory Rule

“In-order pattern: Left $\to$ Node $\to$ Right. Push left nodes onto stack, pop & record, then step right!”

The Big Idea: “Temporary Threads”

In normal tree traversal, a stack or recursion is needed to remember how to get back up after visiting a left subtree.
Morris Traversal achieves $O(1)$ auxiliary space by noticing that leaf nodes have unused null right pointers. It temporarily turns these null pointers into threads (links) pointing back to the current root node, and then destroys them when done.

The 3 Core Rules

For any node curr:

1. If curr has NO left child:
   • Visit curr (add curr.val to result).
   • Move right: curr = curr.right.
2. If curr HAS a left child:
   • Find the in-order predecessor (the rightmost node of the left subtree).
   • First time seeing this link (pred.right == null):
     • Create thread: pred.right = curr (saves our path back).
     • Move left: curr = curr.left.
   • Second time seeing this link (pred.right == curr):
     • Remove thread: pred.right = null (restores original tree structure).
     • Visit curr (add curr.val to result).
     • Move right: curr = curr.right.

Visual Step-by-Step

Consider this tree:

      1
     / \
    2   3
 

1. Start at curr = 1. Has left child 2.
   • Predecessor of 1 is 2.
   • Set 2.right = 1 (thread created).
   • Move to curr = 2.
2. At curr = 2. Has NO left child.
   • **Visit 2**.
   • Move right following thread: curr = 2.right $\to$ returns to 1!
3. At curr = 1. Has left child 2.
   • Predecessor 2 already points to 1 (2.right == 1).
   • Break thread: 2.right = null.
   • **Visit 1**.
   • Move right: curr = 1.right $\to$ 3.
4. At curr = 3. Has NO left child.
   • **Visit 3**.
   • Move right: curr = null (Traversal complete).
     Final Output: [2, 1, 3]

Why It’s Efficient

• Time Complexity: $O(N)$ — Every edge in the tree is traversed at most twice (once to create the thread, once to remove it).
• Space Complexity: $O(1)$ auxiliary space — No stack or recursion stack frame overhead; modifies pointers in-place temporarily.