94. Binary Tree Inorder Traversal
Asked at Google, Anduril
Difficulty
Easy
Time
O(n)
Space
O(h)
Pattern
Stack
Companies
2
Problem
You are given the root of a binary tree. Return a list of all node values in inorder order.
Inorder means the classic left → root → right rule. For every node, you first finish its whole left subtree, then write the node's own value, then walk its right subtree. The same rule applies at every node, so the output is fully determined by the tree shape.
If the tree is empty, return an empty list. The follow-up question is usually: can you do this without recursion? The standard answer uses an explicit stack, which avoids deep recursion on a very tall, one-sided tree.
Inorder = left, root, right
Constraints
- ●
The number of nodes in the tree is in the range [0, 100]. - ●
-100 <= Node.val <= 100
Examples
root = [1,null,2,3][1,3,2]root = [1,2,3,4,5,null,8,null,null,6,7,9][4,2,6,5,7,1,3,9,8]root = [][]Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Anduril | Easy | View all Anduril 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).
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.
Iterative inorder with a stack
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
O(n) timedef 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 runs in O(n) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Binary Tree Inorder Traversal?
Binary Tree Inorder Traversal is asked at Google, Anduril. 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.