DSA · Core pattern
Trees — Basics
Binary trees, traversals, BST property, and the recursion template that solves most tree interview questions.
Simple summary: A tree has one root and child nodes; no cycles.
Example: folders on your computer — open a folder (node), see subfolders (children).
1. Terms
- Root — top node; leaf — no children.
- Height — longest path root to leaf (edges or nodes — state which).
- Binary Search Tree (BST) — left subtree < node < right subtree.
2. Three DFS traversals
Tree: 1
/ \
2 3
In-order (LNR): 2, 1, 3 → sorted order for BST
Pre-order (NLR): 1, 2, 3 → copy/serialize tree
Post-order (LRN): 2, 3, 1 → delete tree bottom-up
3. Recursion template
def solve(node):
if node is None:
return base_answer
left = solve(node.left)
right = solve(node.right)
return combine(node, left, right)
Example — max depth: if node is null return 0; else return 1 + max(left, right).
4. BFS (level order)
Use a queue. Dequeue node, process it, enqueue children. Track level size for "level K" problems.
queue ← root
while queue:
size = len(queue)
for i in 0..size-1:
node = dequeue()
visit(node)
enqueue children
5. Common problems
- Max depth / diameter — DFS with combine step.
- Validate BST — pass min/max range down the tree.
- Lowest Common Ancestor — post-order: if both sides found, current is LCA.
- Level order traversal — BFS with level batching.
6. Complexity
Visit each node once → O(n) time, O(h) stack space where h = height. Skewed tree h = n (worst); balanced h = log n.
Quick revision
- DFS: pre/in/post-order; BFS: queue level by level.
- BST: left < node < right — in-order gives sorted list.
- Template: base on null, recurse left/right, combine.
- Time O(n); space O(h) for recursion.