Pattern Guide
Binary Trees
"Postorder when children decide. Level-order when levels matter."
Master tree traversals (recursive + iterative), level-order with size freeze, tree reconstruction, BST properties, and the "return pair" trick for problems that need both up and down information.
Problems you can solve with this pattern
12 problems · click any to start solving
// Inorder: Left → Root → Right
const inorder = (node) => {
if (!node) return;
inorder(node.left);
process(node.val); // root processed between children
inorder(node.right);
};
// Preorder: Root → Left → Right
const preorder = (node) => {
if (!node) return;
process(node.val); // root first
preorder(node.left);
preorder(node.right);
};
// Postorder: Left → Right → Root
const postorder = (node) => {
if (!node) return;
postorder(node.left);
postorder(node.right);
process(node.val); // root last — children already processed
};Binary tree problems look diverse but the core patterns are just 3-4 traversal strategies. The key skill is recognizing which traversal to use. Preorder when you need to make decisions top-down. Postorder when the parent's decision depends on what the children found. Level-order when problems involve depth or comparing nodes at the same level.
Traversal Decision Matrix
| Use This | When | Why |
|---|---|---|
| Preorder | Build/serialize tree, path problems | Root before children — know the path so far |
| Inorder | BST problems, sorted output | Inorder of BST = sorted sequence |
| Postorder | Delete/modify nodes, size/height, decisions depending on children | Know children's results before deciding for parent |
| Level-order (BFS) | Depth-related, zigzag, right side view | "Freeze" queue size at each level to group nodes |
Core Templates
// Inorder: Left → Root → Right
const inorder = (node) => {
if (!node) return;
inorder(node.left);
process(node.val); // root processed between children
inorder(node.right);
};
// Preorder: Root → Left → Right
const preorder = (node) => {
if (!node) return;
process(node.val); // root first
preorder(node.left);
preorder(node.right);
};
// Postorder: Left → Right → Root
const postorder = (node) => {
if (!node) return;
postorder(node.left);
postorder(node.right);
process(node.val); // root last — children already processed
};const q = [root];
while (q.length > 0) {
const size = q.length; // FREEZE: this level's node count
const level = [];
for (let i = 0; i < size; i++) {
const node = q.shift();
level.push(node.val);
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
// Use i === size-1 to detect last node in level
}
result.push(level);
}const stack = [], result = [];
let node = root;
while (node || stack.length > 0) {
while (node) { // go as far left as possible
stack.push(node);
node = node.left;
}
node = stack.pop(); // process leftmost unprocessed
result.push(node.val);
node = node.right; // now explore right subtree
}Simulate inorder recursion with a stack — O(1) amortized next(), O(h) space.
- kth smallest element (inorder, stop at k)
- Validate BST (check prev < curr in inorder)
- Convert BST to greater tree (REVERSE inorder — right→root→left — accumulate suffix sum)
- Visit children before parent (compute subtree result) → postorder
- Path problems (max path, diameter) → postorder, return best branch, update global max
- Level-by-level (zigzag, right view, connect nodes) → BFS level-order
- BST operations (kth smallest, validate, range) → inorder (gives sorted sequence)
- LCA → postorder, return the node that finds both targets
- Paths from root down → preorder, carry running state (max, sum) as parameter
- Path sum counting → prefix sum + hashmap (backtrack on return)