LeetCode · #94

Binary Tree Inorder Traversal Solution

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

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #94

🏗️

Pattern

Traversal — left → root → right

Given the root of a binary tree, return the inorder traversal of its nodes' values. Inorder visits the left subtree, then the current node, then the right subtree.

Example

 Input: 1
         \
          2
         /
        3
Output: [1, 3, 2]

Constraints

• 0 ≤ number of nodes ≤ 100 • -100 ≤ Node.val ≤ 100

Section Two · Approach 1

Recursive — O(n)

The simplest approach: recurse left, add current value, recurse right. Clean but uses O(h) call stack space.

Java — Recursive

 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> res) {
if (node == null) return;
        inorder(node.left, res);
        res.add(node.val);
        inorder(node.right, res);
    }
}

Python — Recursive

 class Solution:
def inorderTraversal(self, root):
        result = []
def inorder(node):
if not node: return
inorder(node.left)
            result.append(node.val)
            inorder(node.right)
        inorder(root)
return result

Section Three · Approach 2

Iterative with Stack — O(n)

Simulate the call stack explicitly. Push all left children onto the stack, pop one (it's the "current"), process it, then move to its right child and repeat.

💡 Mental model: Go as far left as possible, stacking every node you pass. When you can't go further left, pop the top (leftmost unvisited), record it, then step right and repeat. The stack remembers where to backtrack to.

Algorithm

Step 1: stack = [], curr = root.
Step 2: While curr ≠ null or stack not empty:
Push all left descendants: while curr not null → push, go left.
Pop → record value → move to right child.

🎯 Why learn iterative?:

The follow-up asks for O(1) space (Morris traversal).
The iterative approach is the stepping stone — it makes the recursion explicit, helping you see where Morris eliminates the stack entirely.

Section Four · Trace

Visual Walkthrough

Iterative inorder — tree [1,null,2,3]

Section Five · Implementation

Code — Java & Python (Iterative)

Java — Iterative Stack

 import java.util.*;
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) { // push all lefts
stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop(); // visit
result.add(curr.val);
            curr = curr.right; // go right
}
return result;
    }
}

Python — Iterative Stack

 class Solution:
def inorderTraversal(self, root):
        result, stack, curr = [], [], root
while curr or stack:
while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            result.append(curr.val)
            curr = curr.right
return result

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Recursive	O(n)	O(h) call stack
Iterative stack	O(n)	O(h) explicit stack
Morris traversal	O(n)	O(1)

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty	`null`	Return []. Outer while skips.
Left-skewed	`3→2→1`	Push all three, then pop in order: [1,2,3].
Right-skewed	`1→2→3`	Each node pops immediately, then goes right: [1,2,3].

⚠ Common Mistake: Using only !stack.isEmpty() as the loop condition. When we pop a node and move to its right child, the stack may be empty but curr is non-null — we still have work. Both conditions are needed: curr != null || !stack.isEmpty().

← Back to Trees problems

LearningTree

LC 94 · Binary Tree Inorder Traversal — Solution & Explanation | DSA Guide