5.1 Binary Tree Inorder Traversal

5.1.1 Problem Metadata

5.1.2 Description

Return the inorder traversal (left-root-right) of a binary tree.

5.1.3 Examples

Example 1: Regular Binary Tree

Input:
    1
   / \
  2   3
Output: [2,1,3]
Explanation: In-order visits left subtree first (2), then root (1), then right subtree (3)

Example 2: Empty Tree

Input: null
Output: []

Example 3: Skewed Tree

Input:
    1
     \
      2
       \
        3
Output: [1,2,3]
Explanation: No left children, visits nodes in order down the right spine

5.1.4 Constraints

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

5.1.5 Solution - Iterative Stack

5.1.5.1 Walkthrough

Use a stack to simulate recursion and always dive left first:

  1. Maintain current pointer starting at root.
  2. Traverse left spine: push nodes while moving current = current.left until null.
  3. Pop from stack, record value (the “root” between left and right), then shift to right subtree current = node.right.
  4. Repeat until both current is null and stack is empty.

This yields nodes in left-root-right order without recursion.

5.1.5.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n) worst case stack on a skewed tree

5.1.5.3 Code - Java

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.add(current.val);
        current = current.right;
    }
    return result;
}

5.1.6 Solution - Recursive

5.1.6.1 Walkthrough

Recursively traverse left subtree, visit the current node, then traverse right subtree. This mirrors the inorder definition and appends values in left-root-right order.

The recursive approach is more intuitive and directly reflects the definition of in-order traversal: 1. Base case: If node is null, return immediately 2. Recurse left: Visit all nodes in the left subtree 3. Process current: Add current node’s value to result 4. Recurse right: Visit all nodes in the right subtree

5.1.6.2 Analysis

  • Time Complexity: O(n) - Each node is visited exactly once
  • Space Complexity: O(h) - Recursion call stack depth where h is tree height (O(n) worst case for skewed tree)

5.1.6.3 Code - Java

public List<Integer> inorderTraversalRecursive(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    dfs(root, result);
    return result;
}

private void dfs(TreeNode node, List<Integer> list) {
    if (node == null) {
        return;
    }
    dfs(node.left, list);
    list.add(node.val);
    dfs(node.right, list);
}