Binary Tree Preorder Traversal
Problem Statement
Given the root of a binary tree, return the preorder traversal of its node values. In preorder traversal, visit the current node first, then the left subtree, then the right subtree.
Input
The root pointer of a binary tree, or null for an empty tree.
Output
A list of integers in node, left, right order.
Constraints
- •
0 <= number of nodes <= 100 - •
-100 <= Node.val <= 100
Examples
Example 1
root = [1,null,2,3]
[1,2,3]Example 2
root = []
[]Learning Objectives
- Recognise preorder as the node, left, right DFS order.
- Use preorder when parent work must happen before child work.
- Implement iterative preorder by pushing right before left.
- Explain how stack insertion order controls traversal order.
Intuition
Pattern Recognition
The signal is preorder traversal, root, left, right, serialization, copying, or tree construction where a parent must be handled before its children. Visiting a node means appending its value immediately when the traversal arrives.
The stack trap is subtle: a stack is last-in, first-out. To process the left child next, push the right child first and the left child second. If you push left first, the right subtree comes out before the left subtree.
Common mistakes
- ×Traversing left before appending the node, which no longer produces preorder.
- ×Pushing the left child before the right child in the iterative version.
- ×Pushing **null** children into **ArrayDeque**.
- ×Forgetting that recursive preorder still uses O(h) call-stack space.
Algorithm Explanation
Key idea
Preorder is announce first, descend second. Visit the node, then traverse the left subtree, then traverse the right subtree. The iterative stack stores future work; push right before left so left is popped first.
Recursion walkthrough
Use [1,null,2,3]. Start at 1 and visit it immediately, so the result is [1]. The left child is null, so return. Move to right child 2 and visit it, giving [1,2]. Then recurse into 2's left child 3, visit 3, and finish with [1,2,3] after all null child calls return. The stack version pops 1, pushes 2, then pops 2 and pushes 3 so 3 is next.
Algorithm
- For recursion, return on null.
- Append node.val immediately.
- Recurse into node.left.
- Recurse into node.right.
- For iteration, push root if it exists.
- Pop a node, append it, push its right child, then push its left child.
- Stop when the stack is empty.
Solutions
Solution 1: Recursive preorder DFS
Use this when recursion is allowed and you want the clearest node, left, right implementation.
Visit the current node before making child calls, then recurse left and right in that order.
Step-by-step
- Create an empty result list.
- Call a helper on root.
- Return immediately for null.
- Append node.val.
- Recurse on node.left.
- Recurse on node.right and return the list.
O(n)
O(h)
Every node is visited once; the recursion stack contains at most one root-to-leaf path, O(h) and O(n) when skewed.
Java implementation
Solution 2: Iterative preorder with stack
Use this when recursion is disallowed. The key detail to say aloud is push right then left.
Keep a stack of nodes waiting to be visited. Pop one node, append it, then push its right child before its left child so the left child is processed next.
Step-by-step
- Create an empty result list and stack.
- Push root if it is not null.
- Pop the top node.
- Append its value.
- Push node.right if it exists.
- Push node.left if it exists.
- Repeat until the stack is empty.
O(n)
O(h)
Each node is pushed and popped once; the stack stores the DFS frontier, bounded by height **h** and O(n) worst-case.
Java implementation
Dry Run
Sample input
root = [1,null,2,3]. Track iterative preorder; the top of the stack is shown on the right.
| step | popped | children pushed | stack | result |
|---|---|---|---|---|
| start | none | push root 1 | [1] | [] |
| 1 | 1 | push right child 2 | [2] | [1] |
| 2 | 2 | push left child 3 after checking right | [3] | [1,2] |
| 3 | 3 | no children | [] | [1,2,3] |
The result grows as soon as a node is popped. Pushing right before left preserves node, left, right order.
Interview Tips
Preorder is parent-first. That makes it natural for serialization with null markers, cloning, and reconstruction when paired with inorder. In the iterative solution, say push right then left before writing code; it shows you understand how the stack determines order.
Likely follow-ups
- How would you include **null** markers to serialize a tree with preorder?
- How does preorder plus inorder reconstruct a unique tree?
- Can you write the traversal with an explicit stack?
- How would you collect root-to-leaf paths using a preorder DFS?
Similar Problems
Key Takeaways
- Preorder means **node, left, right**.
- Visiting happens immediately when the traversal reaches a node.
- The iterative stack must push right before left.
- Preorder is the parent-first traversal used in serialization and construction.