10. Binary Tree Inorder Traversal
easyAsked at CoinbaseReturn 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 Sam K., 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
root = [1,null,2,3][1,3,2]Example 2
root = [][]Example 3
root = [1][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.
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.