Skip to main content

10. Binary Tree Inorder Traversal

easyAsked at Coinbase

Return the inorder traversal of a binary tree's values. Coinbase asks this to confirm you can do both recursive and iterative tree walks — iterative is the one you'd use to walk a price-level tree without blowing the stack.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Coinbase loops.

  • Glassdoor (2026-Q1)— Coinbase backend phone screen.

Problem

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

Constraints

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

Examples

Example 1

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

Example 2

Input
root = []
Output
[]

Example 3

Input
root = [1]
Output
[1]

Approaches

1. Recursive DFS

Recurse left, visit, recurse right.

Time
O(n)
Space
O(h) recursion stack
function inorderTraversal(root) {
  const out = [];
  function walk(node) {
    if (!node) return;
    walk(node.left);
    out.push(node.val);
    walk(node.right);
  }
  walk(root);
  return out;
}

Tradeoff: Simple but O(h) stack — for skewed trees (h=n) you risk overflow.

2. Iterative with explicit stack

Push left spine onto a stack. Pop a node, visit it, then descend its right child's left spine. Repeat until stack and current are both empty.

Time
O(n)
Space
O(h)
function inorderTraversal(root) {
  const out = [];
  const stack = [];
  let curr = root;
  while (curr || stack.length) {
    while (curr) {
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();
    out.push(curr.val);
    curr = curr.right;
  }
  return out;
}

Tradeoff: Heap-allocated stack avoids native-stack overflow. Same O(n) time, easier to reason about pause/resume.

Coinbase-specific tips

Coinbase grades iterative over recursive for production-shape problems — they'll often ask 'now make it resumable so we can stream rows out one at a time.' Be ready to refactor the iterative version into a generator. The traversal-as-iterator pattern is what their order-book snapshotter uses.

Common mistakes

  • Forgetting the inner while loop that walks down the left spine.
  • Visiting the node before the left subtree — that's preorder, not inorder.
  • Not handling root == null — the outer while guards on it.

Follow-up questions

An interviewer at Coinbase may pivot to one of these next:

  • Convert to a generator that yields one value at a time.
  • Morris traversal — O(1) space using threaded pointers.
  • Iterative preorder and postorder.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why iterative when recursive is shorter?

Stack overflow risk on skewed trees and the inability to pause/resume. For a production tree walker (paginated, streaming) iterative is mandatory.

What's Morris traversal?

A trick where you temporarily rewrite the right pointer of each inorder-predecessor to point to its successor, walk forward, then restore. O(1) extra space, but mutates the tree during the walk.

Practice these live with InterviewChamp.AI

Drill Binary Tree Inorder Traversal and other Coinbase interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →