144. Binary Tree Preorder Traversal
Asked at Microsoft
Difficulty
Easy
Time
O(n)
Space
O(h)
Pattern
Stack
Companies
1
Problem
You are given the root of a binary tree. Return a list of all node values in preorder: visit a node first, then walk its entire left subtree, then walk its entire right subtree.
So for every node, the order is node → left → right. The list must contain exactly one value per node, in that order.
The follow-up asks you to do it iteratively (with your own stack) instead of using recursion.
Preorder: node, then left, then 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,2,3]root = [1,2,3,4,5,null,8,null,null,6,7,9][1,2,4,5,6,7,3,8,9]root = [][]root = [1][1]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Microsoft | Easy | View all Microsoft questions → |
How to Think About It
Baseline: recursion visits node, then left subtree, then right subtree in O(n) time with O(h) recursion depth. The iterative version removes the call stack and runs safely even on deeply skewed trees.
Key insight: since the node itself must be output first, you can emit it the moment the stack produces it - there is no need to hold any node waiting for its left subtree to drain.
The stack pattern: push the right child first, then the left child. Because the stack is LIFO, the left child pops first, which automatically produces node, left subtree, right subtree.
Why pushing right before left works: LIFO order means the last pushed child is processed next. Pushing right then left puts left on top, matching the preorder contract of visiting left before right.
Edge cases: a null root must return [] before any push; a single node returns that node; both children of a popped node may be null and must be skipped safely.
Optimal Approach
Preorder visits the current node, then its left subtree, then its right subtree. Iteratively, seed a stack with the root. Pop a node, record its value, then push its right child followed by its left child so the left child is popped and processed next.
Walkthrough on the tree where root 1's right child is 2 and 2's left child is 3:
- Stack starts
[1]. Pop 1, record 1, push right child 2. Stack[2]. - Pop 2, record 2, push right (null, skipped) and left child 3. Stack
[3]. - Pop 3, record 3. Stack empty. Result
[1, 2, 3].
Time: O(n) space: O(h) - the stack never holds more than one root-to-leaf branch.
Stack: push right, then left
What Trips People Up in Real Interviews
Pushing the left child before the right child. LIFO then processes right first, and the output becomes node-right-left, which is not preorder. Always push right, then left.
Not guarding against a null root. Popping a null node, or pushing null children, either crashes or pollutes the result with null values. Check the root and each child before pushing.
Coding recursion and stopping there. Preorder is trivially recursive, but interviewers often push for the stack-based version - explain the recursion limit problem and convert to an explicit stack.
Confusing preorder emission timing with inorder. Inorder emits on pop after the left subtree drains; preorder emits immediately when the node is on top. Mixing these produces output that is neither traversal.
Adding a visited set or a second container. A single stack fully describes preorder - extra bookkeeping wastes space and shows you do not trust the LIFO invariant.
Solution Code
O(n) timedef preorderTraversal(root):
res = []
stack = [root]
while stack:
node = stack.pop()
if node:
res.append(node.val)
stack.append(node.right)
stack.append(node.left)
return resFrequently Asked Questions
What is the Binary Tree Preorder Traversal problem?
Return the preorder traversal of a binary tree, visiting each node before its left and right children. It is the simplest of the three DFS orders to write iteratively with a stack and a common Microsoft warm-up for tree recursion patterns.
How do you solve Binary Tree Preorder 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 Preorder Traversal?
Binary Tree Preorder Traversal is asked at Microsoft. It is a easy difficulty problem.
What are common mistakes on Binary Tree Preorder Traversal?
- Pushing the left child before the right child. LIFO then processes right first, and the output becomes node-right-left, which is not preorder. Always push right, then left.
- Not guarding against a null root. Popping a null node, or pushing null children, either crashes or pollutes the result with null values. Check the root and each child before pushing.
- Coding recursion and stopping there. Preorder is trivially recursive, but interviewers often push for the stack-based version - explain the recursion limit problem and convert to an explicit stack.
- Confusing preorder emission timing with inorder. Inorder emits on pop after the left subtree drains; preorder emits immediately when the node is on top. Mixing these produces output that is neither traversal.
- Adding a visited set or a second container. A single stack fully describes preorder - extra bookkeeping wastes space and shows you do not trust the LIFO invariant.