#94 Binary Tree Inorder Traversal

Problem Statement

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Intuition

Inorder traversal visits nodes in left-root-right order, which for a BST produces sorted output. The recursive version is straightforward; the iterative version uses a stack to simulate the call stack.

Approach

1. Initialize an empty result array and a stack.
2. Start with the current node as root.
3. Go as far left as possible, pushing nodes onto the stack.
4. Pop from the stack, add the value to the result, then move to the right child.
5. Repeat until the stack is empty and current is null.

Solution

function inorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack: TreeNode[] = [];
  let current = root;

  while (current || stack.length > 0) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop()!;
    result.push(current.val);
    current = current.right;
  }

  return result;
}

Complexity Analysis