#144
Binary Tree Preorder Traversal
Easy Iterative preorder with a stack
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the values of a binary tree in preorder (node, left subtree, right subtree).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: node first, then left, then right.
Why this works: with a stack, pop and visit; push right before left so left comes out first.
Example: tree 1 (left 2, right 3)
pop 1 → push 3, 2pop 2, pop 3 → [1, 2, 3]
✦Hints open one at a time
Visit a node as soon as you pop it.
Push the right child before the left so the left is processed first.
↗Approach
Stack starts with root. Pop, record, push right then left.
</>Solution (Java)
import java.util.*;
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> st = new ArrayDeque<>();
st.push(root);
while (!st.isEmpty()) {
TreeNode n = st.pop();
res.add(n.val);
if (n.right != null) st.push(n.right); // right first, so left pops first
if (n.left != null) st.push(n.left);
}
return res;
}
}!Common mistake
Pushing left before right, which produces node-right-left order.
Complexity
- Time: O(n).
- Space: O(h).
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon