/Interview Study Guide/Algorithms & data structures
#18

Binary Tree Inorder Traversal

easy
Open in editor
stacktreedepth-first-searchbinary-tree

Given the root of a binary tree, return the inorder traversal of its nodes' values — left subtree, then node, then right subtree.

The tree is given as a level-order array where null marks a missing child: [1, null, 2, 3] is a root 1 whose right child is 2, and 2's left child is 3.

Example

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

Visit 1, then 2's left child 3, then 2.

Constraints

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

Intuition

In-order traversal visits the left subtree, then the node, then the right subtree. The most direct implementation is the literal recursion: recurse left, record the value, recurse right.

function inorderTraversal(root) {
  const result = [];
  const visit = (node) => {
    if (!node) return;
    visit(node.left);     // left subtree first
    result.push(node.val); // then the node
    visit(node.right);    // then the right subtree
  };
  visit(root);
  return result;
}
Brute force — straightforward recursion, appending into a shared array: O(n) time, O(h) stack.

The recursion is clean and O(n), but it leans on the call stack — interviewers often ask for it iteratively, and a very deep tree can overflow that stack. Can we do it without recursion?

The key observation: an explicit stack can stand in for the call stack. Walk left as far as possible, pushing every node; when you can't go left, pop a node, record it (that's the in-order moment), and step into its right child. Repeat until both the stack and the current pointer are exhausted.

The lane is the in-order output of [1, null, 2, 3] — root 1, right child 2, and 2's left child 3 — which is [1, 3, 2]:

in-order output of [1, null, 2, 3] → [1, 3, 2]

out↓
1
3
2
push 1; left is null → pop, record 1

Start at root 1. No left child, so 1 is recorded first.

out↓
1
3
2
step right to 2, then left to 3

Move into 1's right (2), then dive left to 3, pushing as we go.

1
out↓
3
2
pop, record 3

3 has no left child → it's the next in-order value.

1
3
out↓
2
pop, record 2

Back up to 2 and record it. Result: [1, 3, 2].

Optimization

Iterative with an explicit stack

Walk left as far as possible, pushing every node; when you can't go left, pop, record the value, and step right. The stack stands in for the recursion call stack, so it's iterative without extra recursion depth.

O(n) time, O(h) space for the stack (tree height h).

function inorderTraversal(root) {
  const result = [];
  const stack = [];
  let curr = root;
  while (curr || stack.length) {
    while (curr) {
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();
    result.push(curr.val);
    curr = curr.right;
  }
  return result;
}

Complexity analysis

Time complexity: O(n). Here's why:

  • Each node is pushed and popped exactly once.

So O(n).

Space complexity: O(h). Here's why:

  • The explicit stack holds at most one root-to-leaf path — O(h).

O(log n) balanced, O(n) for a skewed tree. The output array is the unavoidable result.

Test cases

Beyond the example above, these are worth thinking through before you submit.

InputExpected outputDescription
root = []null[]Empty tree.
root = [9]9[9]Single node.
root = [5,3,8]358[3,5,8]A balanced BST: in-order is sorted.
root = [5,null,6,null,7]567[5,6,7]A right spine: still left-node-right order.
root = [7,6,null,5]567[5,6,7]A left spine yields ascending order too.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor