Skip to main content

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

Algorithm Flow​

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

currstackresultaction
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​

ApproachTimeSpace
RecursiveO(n)O(h)
IterativeO(n)O(h)
MorrisO(n)O(1)

Key Terms​

TermDefinition
Inorder traversalVisit order left → node → right; produces sorted output for a BST
Iterative stack simulationUsing an explicit stack to replace the recursion call stack
Recursion depth (h)Height of the tree; bounds the auxiliary space used by DFS
Morris traversalO(1)-space traversal using temporary threaded links to predecessors

FAQ​

Q1: Can inorder traversal be done without extra space? Yes — Morris Traversal achieves O(1) space by temporarily threading each node's inorder predecessor's right pointer to itself, then restoring it after visiting.

Q2: What does inorder traversal return for an empty tree? An empty list [], since dfs(None) or the iterative while curr or stack loop never executes.

Q3: Why does inorder traversal produce sorted output for a BST? Because a BST's left subtree holds smaller values and right subtree holds larger values; visiting left → node → right walks values in ascending order.

Q4: How would you get preorder or postorder instead? Change the visit order: record node.val before recursing (preorder) or after both children (postorder). The iterative versions need a modified stack strategy since postorder in particular needs to track visited state.

Q5: How does the iterative approach avoid stack overflow on deep trees? It uses a heap-allocated Python list as an explicit stack instead of the language's call stack, avoiding Python's recursion limit (though O(h) space is still consumed).

Quick Revision​

  • Inorder order: left → root → right.
  • Recursive solution: base case on None, recurse left, append, recurse right.
  • Iterative solution: push left children onto a stack until None, pop, record, move to .right.
  • Loop condition is while curr or stack — both must be checked since the last pop may have a right child to descend into.
  • Time is always O(n) since every node is visited exactly once.
  • Space is O(h): O(log n) for balanced trees, O(n) worst case for skewed trees.
  • Morris traversal trades code complexity for O(1) space by threading predecessor links.
  • For a BST, inorder traversal yields values in sorted order — useful for validation problems.