Preorder Traversal
Mahabharata — The Commander First — Root, Then Left Army, Then Right Army
मूल पहले — फिर बायां — फिर दायां। Preorder में सेना — मुखिया प्रथम, फिर टुकड़ी॥
*Root first — then left — then right. Army in preorder — commander first, then troops.*
The Story
Perform preorder traversal (Root → Left → Right) of a binary tree.
For tree `[1,2,3]` (root=1, left=2, right=3): Preorder=[1,2,3].
**Recursive:** ```java void preorder(TreeNode root, List<Integer> res) { if (root == null) return; res.add(root.val); // Root first preorder(root.left, res); // Left preorder(root.right, res); // Right } ```
**Iterative (Stack):** Visit root first, then push RIGHT child before LEFT (so LEFT is processed first — stack is LIFO): ```java Deque<TreeNode> st = new ArrayDeque<>(); st.push(root); while (!st.isEmpty()) { root = st.pop(); res.add(root.val); // Visit if (root.right != null) st.push(root.right); // Right pushed first if (root.left != null) st.push(root.left); // Left pushed last (processed first) } ```
**Use cases for preorder:** - Copy/serialize a tree (root before children) - Construct a tree from preorder + inorder - Prefix expressions (operator before operands) - Directory listing (folder before contents)
Trace `[1,2,3]`: - Push 1. Pop 1, add 1, push 3, push 2. - Pop 2, add 2. No children. - Pop 3, add 3. No children. - Result=[1,2,3] ✓
The Level-Order Approach
BFS visits level by level (not preorder). Preorder IS the standard approach.
// Preorder is already optimal. Recursive:
void preorderRecursive(TreeNode root, List<Integer> res) {
if (root == null) return;
res.add(root.val);
preorderRecursive(root.left, res);
preorderRecursive(root.right, res);
}The Root-First Stack Wisdom
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()) {
root = st.pop();
res.add(root.val);
if (root.right != null) st.push(root.right);
if (root.left != null) st.push(root.left);
}
return res;
}Step-by-Step Walkthrough
Single node [1]: push 1. Pop 1, add 1, no children. Result=[1] ✅
Deep Insight
**Stack push order trick:** Push right BEFORE left so that left is popped first (LIFO). This ensures left subtree is processed before right, matching preorder (Root-Left-Right).
**Preorder vs Inorder iterative pattern:** - Preorder: Push root → pop → visit → push right → push left - Inorder: Keep pushing left until null → pop → visit → go right
**Preorder for tree reconstruction:** Given preorder + inorder, we can reconstruct the unique binary tree. The first element of preorder is always the root.
**Preorder IS DFS:** Depth-first search of a binary tree in preorder visits nodes in DFS order.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Recursive call stack or explicit stack |
| Optimal | O(n) | O(n) | Stack size = height of tree = O(n) worst case |
Pattern Recognition
✅ Preorder = Root, Left, Right ✅ Iterative: push root; pop, visit, push right, push left ✅ Push right BEFORE left (LIFO ensures left first) ✅ Use case: tree copy, serialization **LeetCode Trigger Phrases:** → "preorder traversal" → Visit root before subtrees → Tree serialization / reconstruction
Bhagavad Gita 5.29
मैत्रः करुण एवाहं सर्वलोकमहेश्वरः।
I am the well-wishing friend of all creatures and the Supreme Lord of all.
Connection: Preorder traversal begins with the root — the source, the lord, the origin — before descending into the left and right subtrees. Like the divine who is known first as the supreme source from which all branches of creation emanate, the preorder visits the root before exploring what grows from it. Each node is encountered first as itself before its children are explored — the commander seen before the troops he commands.