94 - Binary Tree Inorder Traversal

Difficulty: Easy | Pattern: Tree DFS / Iterative Stack | Company tags: Amazon, Microsoft, Google

Problem Statement

Given the root of a binary tree, return the inorder traversal of its nodes' values (left → root → right).

Example 1:

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

Example 2:

Input: root = []
Output: []

Approach 1: Recursive — O(n), O(h)

def inorderTraversal(root) -> list[int]:
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)
    dfs(root)
    return result

Approach 2: Iterative (Stack) — O(n), O(h)

Key insight: Push nodes left as far as possible, pop and record, then go right.

def inorderTraversal(root) -> list[int]:
    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

Dry Run

Tree: 1 → right: 2 → left: 3

curr	stack	result	action
1	[]	[]	push 1, go left (None)
None	[1]	[]	pop 1, record 1, go right
2	[]	[1]	push 2, go left
3	[2]	[1]	push 3, go left (None)
None	[2,3]	[1]	pop 3, record 3, go right (None)
None	[2]	[1,3]	pop 2, record 2, go right (None)

Result: [1,3,2] ✓

Edge Cases

• Empty tree → []
• Single node → [val]
• Left-skewed tree → O(n) stack depth

Complexity

Approach	Time	Space
Recursive	O(n)	O(h)
Iterative	O(n)	O(h)
Morris	O(n)	O(1)

Study Snapshot

94 - Binary Tree Inorder Traversal introduces problem pattern, invariant, edge cases, and complexity. Use the page to build a clear mental model, connect the parts, and practice explaining the idea with an example.

Concept Primer

This is likely a tree traversal or recursion problem. Identify the base case first, decide whether the answer is built from the left child, right child, or both, and test a single-node tree before a larger tree. Common edge cases are empty trees, skewed trees, duplicate values, and very deep recursion.

How to Understand This Topic

• Create one example for 94 - Binary Tree Inorder Traversal using the page's terms before moving to revision.
• Finish by asking what assumption, exception, or limitation would change the answer. Do not stop at the final code. Explain why the pattern works and where it fails.

Concept Flow

What Each Section Adds

Section	What It Adds to Your Understanding
Core idea	Define 94 - Binary Tree Inorder Traversal in one plain sentence.
Example	Create one small scenario where the idea is visible.
Limitation	Name one assumption, exception, or missing detail that could change the answer.

Relatable Example

algorithm dry run: Use a deliberately small input, write the changing variables after each step, and then try one empty or boundary case. Take a tiny input and trace it by hand before coding. For 94 - Binary Tree Inorder Traversal, write the state after each important step, then ask which invariant stayed true and which edge case could break the approach. This turns the page from a solution to memorize into a pattern you can reuse in interviews.

Check Your Understanding

1. What is the simplest correct definition of 94 - Binary Tree Inorder Traversal?
2. What example would make the idea concrete for a beginner?
3. What assumption, exception, or limitation should be mentioned for a complete answer in Software Engineering Interview Prep?

Improve Your Answer

• Start with a plain-English definition before using technical terms.
• Anchor the answer in the page's real sections: 94 - Binary Tree Inorder Traversal.
• Add one concrete example, then state the limitation or exception that keeps the answer honest.
• Use keywords naturally for search and revision: 94 - Binary Tree Inorder Traversal.

What to Review Next

• Revisit 94 - Binary Tree Inorder Traversal and explain each item without rereading the paragraph.
• Add one self-made example that uses the exact vocabulary of 94 - Binary Tree Inorder Traversal.
• Compare this page with the next related topic and note one similarity, one difference, and one open question.