Binary Tree Inorder Traversal
Asked at Google
Problem
Given the root of a binary tree, return the inorder traversal of its nodes' values as a list. This asks for the classic left-root-right order and tests whether you can write the iterative version using an explicit stack, which is the standard Google warm-up for tree problems.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → |
How to Think About It
Baseline: recursion visits left, then node, then right in O(n) time. It is the simplest to write but consumes O(n) call-stack space in the worst case and can overflow on a deeply skewed tree, which is why the iterative version is usually required.
Key insight: inorder means left-root-right, so you must never emit a node until its entire left subtree is drained. An explicit stack mirrors the recursive call stack without hitting recursion limits.
The iterative pattern: push every left child onto the stack, descending left until null. Only then pop a node, emit it, and move to its right child, where the whole left-descending process repeats.
Why the two-phase loop is correct: the stack always holds nodes whose left subtree is still in progress. When you pop, that node's left side is already fully output, so emitting it now preserves order; then you descend right. Every node is pushed and popped exactly once, so it is O(n).
Visual walkthrough for the tree [1, null, 2, 3] (1's right child is 2, whose left child is 3):
- cur=1: push 1, descend to null.
- pop 1, output [1], cur=1.right=2.
- cur=2: push 2, descend left to 3; push 3, descend to null.
- pop 3, output [1,3], cur=3.right=null.
- pop 2, output [1,3,2], cur=2.right=null.
Result: [1, 3, 2].
Edge cases: empty tree returns []; a single node returns [val]; a fully left-skewed tree exercises the stack drain of O(n) depth.
Optimal Approach
Iterative inorder uses an explicit stack. Start with an empty stack and a pointer cur at the root. While cur is not null, push cur and descend to cur.left. When cur becomes null, pop a node, append its value, and move cur to the popped node's right child. Repeat until the stack is empty and cur is null.
Walkthrough on the tree with root 1, left child 2 and right child 3:
cur=1: push 1, descend left to node 2. Push 2, descend left to null.- Pop 2, output 2,
cur = 2.right = null. - Pop 1, output 1,
cur = 1.right = 3. - Push 3, descend left to null. Pop 3, output 3.
Result:[2, 1, 3].
Time: O(n) space: O(h) for the stack, which is O(n) worst case on a skewed tree.
What Trips People Up in Real Interviews
Recursing without ever stating the iterative requirement. Many interviewers specifically ask for the explicit-stack version. Say: "Recursion first for clarity, then I'll convert it to an explicit stack to avoid overflow."
Popping a node before its left subtree is finished. Emission must wait until you have descended fully left - popping immediately after pushing produces preorder output, not inorder.
Forgetting to move to the right child after popping. If you do not set cur to popped.right, the loop stops early and every right subtree is silently skipped.
Adding a visited set or marker on top of the stack. That is unnecessary and signals confusion - the descend-left loop alone guarantees each node is processed once. Extra structures inflate space to O(n).
Using the wrong loop condition. The loop must run while the stack is non-empty OR cur is non-null. Checking only the stack misses the very first node when the tree has a root but the stack starts empty.
Solution Code
def inorderTraversal(root):
res = []
stack = []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return resFrequently Asked Questions
What is the Binary Tree Inorder Traversal problem?
Given the root of a binary tree, return the inorder traversal of its nodes' values as a list. This asks for the classic left-root-right order and tests whether you can write the iterative version using an explicit stack, which is the standard Google warm-up for tree problems.
How do you solve Binary Tree Inorder Traversal?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Binary Tree Inorder Traversal?
Binary Tree Inorder Traversal is asked at Google. It is a easy difficulty problem.
What are common mistakes on Binary Tree Inorder Traversal?
- Recursing without ever stating the iterative requirement. Many interviewers specifically ask for the explicit-stack version. Say: "Recursion first for clarity, then I'll convert it to an explicit stack to avoid overflow."
- Popping a node before its left subtree is finished. Emission must wait until you have descended fully left - popping immediately after pushing produces preorder output, not inorder.
- Forgetting to move to the right child after popping. If you do not set `cur` to `popped.right`, the loop stops early and every right subtree is silently skipped.
- Adding a visited set or marker on top of the stack. That is unnecessary and signals confusion - the descend-left loop alone guarantees each node is processed once. Extra structures inflate space to `O(n)`.
- Using the wrong loop condition. The loop must run while the stack is non-empty OR `cur` is non-null. Checking only the stack misses the very first node when the tree has a root but the stack starts empty.