Binary Tree InOrder Traversal

leetcode.com

Problem Statement

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

Inorder Traversal follows:

Left

↓

Root

↓

Right

---

Brute Force Intuition

In an interview, you can explain it like this:

Visit the left subtree first, then the current node, and finally the right subtree. This naturally follows recursion.

Recursion automatically remembers the path back to parent nodes.

Complexity

• Time Complexity: O(N)
• Space Complexity: O(H)

Where:

• N = Number of Nodes
• H = Height of Tree

Recursive Code

class Solution {

    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> ans = new ArrayList<>();

        inorder(root, ans);

        return ans;
    }

    private void inorder(TreeNode root,
                         List<Integer> ans) {

        if (root == null)
            return;

        inorder(root.left, ans);

        ans.add(root.val);

        inorder(root.right, ans);
    }
}

---

Moving Towards the Optimal Iterative Approach

Recursion uses the call stack.

Can we simulate it ourselves?

Yes.

Use an explicit:

Stack

Go left as much as possible.

Process node.

Move to right.

---

Pattern Recognition

Whenever you see:

• Tree Traversal
• Simulate Recursion

Think:

Stack

---

Optimal Java Solution (Iterative)

class Solution {

    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> ans = new ArrayList<>();

        Stack<TreeNode> st = new Stack<>();

        TreeNode curr = root;

        while (curr != null || !st.isEmpty()) {

            while (curr != null) {

                st.push(curr);

                curr = curr.left;
            }

            curr = st.pop();

            ans.add(curr.val);

            curr = curr.right;
        }

        return ans;
    }
}

---

Dry Run

        1
         \
          2
         /
        3

Traversal:

Left

↓

Root

↓

Right

Answer:

1 3 2

---

Why Stack Works?

The stack stores parent nodes while moving left.

Once the left subtree finishes,

we process the parent and continue with its right subtree.

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(H)

---

Interview One-Liner

Use a stack to simulate recursion by visiting all left nodes first, then processing the node, and finally exploring the right subtree.

---

Pattern Learned

Left

↓

Root

↓

Right

Similar Problems

• Inorder Traversal
• BST Iterator
• Morris Traversal
• Recover BST

---

Memory Trick

Go Left

↓

Pop

↓

Visit

↓

Go Right

Whenever you hear:

"Inorder Traversal"

your brain should immediately think:

Left → Root → Right