Binary Tree Inorder Traversal

Difficulty: Easy

Problem

Given the root of a binary tree, return the inorder traversal of its nodes' values. Inorder traversal visits: Left subtree, then Root, then Right subtree.

Example

Input: root = [1,null,2,3]
Output: [1,3,2]
Explanation: Inorder: go left (empty), visit 1, go right to 2, go left to 3, visit 3, visit 2.

Brute-force approach

Use recursion to traverse the tree: go left, visit node, go right. This is the natural recursive approach and is actually the standard solution for this problem.

Steps

  1. If the current node is null, return (base case)
  2. Recursively traverse the left subtree
  3. Add the current node's value to the result
  4. Recursively traverse the right subtree

Time complexity: O(n) · Space complexity: O(n) — O(h) for call stack + O(n) for result array

Trade-offs

  • Uses O(h) stack space due to recursion (O(n) worst case for skewed trees)
  • Risk of stack overflow for very deep trees
  • Cannot pause/resume traversal easily

Optimal approach

Key insight: Inorder traversal follows a simple pattern: fully explore the left subtree first, then visit the current node, then fully explore the right subtree. The recursion naturally handles the ordering.

The recursive approach IS the clean optimal solution for inorder traversal. An alternative iterative approach using an explicit stack avoids recursion overhead and stack overflow risk, but both are O(n) time and O(h) space.

Steps

  1. Base case: If node is null, return immediately
  2. Recurse into the left child (explore entire left subtree)
  3. Visit current node: append its value to the result list
  4. Recurse into the right child (explore entire right subtree)

Time complexity: O(n) · Space complexity: O(h) where h = height of tree