Binary Tree Preorder Traversal
Asked at Microsoft
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.
Asked At
| 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.
Visual walkthrough for the tree [1, 2, 3, 4] (2 and 3 are children of 1, 4 is the left child of 2):
- push 1. pop 1, output [1], push right 3, push left 2. stack=[3,2]
- pop 2, output [1,2], push 2.right (null), push 4. stack=[3,4]
- pop 4, output [1,2,4]. stack=[3]
- pop 3, output [1,2,4,3]. stack=[]
Result: [1, 2, 4, 3].
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.
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
def 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 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 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.