Given the root of a binary tree, return the inorder traversal of its nodes’ values. Inorder visits: left → root → right.

Examples

Example 1:

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

Example 2:

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

Example 3:

Input: root = []
Output: []

Constraints

  • The number of nodes is in [0, 100]
  • -100 <= Node.val <= 100

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Thinking Process

Inorder traversal processes nodes in left → root → right order. For a BST, this produces sorted output.

Three standard implementations:

  1. Recursive – direct translation
  2. Iterative (stack) – go as far left as possible, then process and go right
  3. Morris traversal – O(1) auxiliary space using threaded tree

Iterative Key Insight

Unlike preorder where we can simply push right then left, inorder requires us to defer visiting a node until its entire left subtree is processed. The pattern is: push all left children onto the stack, pop and visit, then move to the right child.

Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

Approach 1: Recursive – O(n)

Input: root = [1,null,2,3]
Output: [1,3,2]
# Tree:  1
#         \
#          2
#         /
#        3

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: Inorder traversal processes nodes in left → root → right order. For a BST, this produces sorted output.

How the code works:

  1. Recursive – direct translation
  2. Iterative (stack) – go as far left as possible, then process and go right
  3. Morris traversal – O(1) auxiliary space using threaded tree

Walkthrough — input root = [1,null,2,3], expected output [1,3,2]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Approach 2: Iterative (Stack) – O(n)

Push all left children first. When there’s nothing left to go, pop, visit, and move right.

Input: root = []
Output: []

Time: O(n) Space: O(n) for the output; O(h) for the stack

Approach 3: Morris Traversal – O(n)

Thread the rightmost node of the left subtree back to the current node. Visit the node after returning via the thread (between left and right).

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

Time: O(n) Space: O(n) for the output; O(1) auxiliary

Comparison

Approach Time Space Notes
Recursive O(n) O(h) aux Simplest
Iterative Stack O(n) O(h) aux “Go left, pop, go right” pattern
Morris O(n) O(1) aux Modifies tree temporarily, restores it

Preorder vs Inorder: Key Difference

The Morris and iterative templates are almost identical across traversal orders. The only difference is when you record the node’s value:

Order Record when…
Preorder Before going left (first visit)
Inorder After returning from left (second visit / thread return)

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  • Iterative inorder = “go left as far as possible, pop, visit, go right” – this is the most commonly tested iterative pattern
  • Morris inorder visits the node when it encounters the thread for the second time (thread already exists), unlike preorder which visits on the first encounter
  • For a BST, inorder traversal yields sorted order – useful for validation and kth-element problems

References

Template Reference