Binary Trees
Traversals (recursive, iterative, level-order), the 'return info up / pass info down' mindset, path problems, lowest common ancestor, and serialization.
Vocabulary
A binary tree is a set of nodes where each node has at most two children: left and right.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val, self.left, self.right = val, left, right
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x = 0) : val(x), left(nullptr), right(nullptr) {}
};
| Term | Meaning |
|---|---|
| root / leaf | top node / node with no children |
| depth of a node | edges from the root to it |
| height of a tree | max depth (edges or nodes — be explicit!) |
| full | every node has 0 or 2 children |
| complete | all levels full except possibly the last, filled left to right (heaps) |
| perfect | all internal nodes have 2 children, all leaves at the same depth: 2^(h+1) − 1 nodes |
| balanced | heights of the two subtrees of every node differ by ≤ 1 → height O(log n) |
Traversals
1
/ \
2 3
/ \
4 5
Pre-order (root, L, R): 1 2 4 5 3
In-order (L, root, R): 4 2 5 1 3
Post-order (L, R, root): 4 5 2 3 1
Level-order (BFS): 1 2 3 4 5
Watch them animate in the tree traversal visualizer.
Recursive
def inorder(root, out):
if not root:
return
inorder(root.left, out)
out.append(root.val) # move this line for pre/post-order
inorder(root.right, out)
Iterative in-order (know this one)
def inorder_iter(root):
out, stack, cur = [], [], root
while cur or stack:
while cur: # go as far left as possible
stack.append(cur)
cur = cur.left
cur = stack.pop()
out.append(cur.val)
cur = cur.right
return out
vector<int> inorderTraversal(TreeNode* root) {
vector<int> out; stack<TreeNode*> st; TreeNode* cur = root;
while (cur || !st.empty()) {
while (cur) { st.push(cur); cur = cur->left; }
cur = st.top(); st.pop();
out.push_back(cur->val);
cur = cur->right;
}
return out;
}
Iterative post-order trick: do a pre-order with (root, R, L) and reverse the output.
Level-order (BFS)
from collections import deque
def level_order(root):
if not root:
return []
res, q = [], deque([root])
while q:
level = []
for _ in range(len(q)): # exactly the nodes of this level
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
res.append(level)
return res
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> q; q.push(root);
while (!q.empty()) {
int sz = q.size();
res.push_back({});
while (sz--) {
TreeNode* n = q.front(); q.pop();
res.back().push_back(n->val);
if (n->left) q.push(n->left);
if (n->right) q.push(n->right);
}
}
return res;
}
Level-order variants: zigzag, right side view, level averages, minimum depth (first leaf found), connect next pointers, max width (store positional indices 2i, 2i+1).
The two ways information flows
Nearly every tree problem is one of these (or both):
Top-down example: count good nodes
def good_nodes(root):
def dfs(node, max_so_far):
if not node:
return 0
good = 1 if node.val >= max_so_far else 0
m = max(max_so_far, node.val)
return good + dfs(node.left, m) + dfs(node.right, m)
return dfs(root, float("-inf"))
Bottom-up example: diameter
The longest path through a node = height(left) + height(right). Compute heights bottom-up and update a global best.
def diameter(root):
best = 0
def height(node):
nonlocal best
if not node:
return 0
l, r = height(node.left), height(node.right)
best = max(best, l + r) # path through this node (in edges)
return 1 + max(l, r) # what the parent needs
height(root)
return best
int diameterOfBinaryTree(TreeNode* root) {
int best = 0;
function<int(TreeNode*)> height = [&](TreeNode* n) {
if (!n) return 0;
int l = height(n->left), r = height(n->right);
best = max(best, l + r);
return 1 + max(l, r);
};
height(root);
return best;
}
Maximum path sum
def max_path_sum(root):
best = float("-inf")
def gain(node):
nonlocal best
if not node:
return 0
l = max(gain(node.left), 0) # drop negative branches
r = max(gain(node.right), 0)
best = max(best, node.val + l + r)
return node.val + max(l, r)
gain(root)
return best
Returning multiple values
When the parent needs several facts, return a tuple.
def is_balanced(root):
def check(node): # returns (balanced, height)
if not node:
return True, 0
lb, lh = check(node.left)
rb, rh = check(node.right)
return lb and rb and abs(lh - rh) <= 1, 1 + max(lh, rh)
return check(root)[0]
This is the doorway to tree DP: e.g. House Robber III returns (best if robbed, best if not robbed). See Advanced DP.
Lowest common ancestor
def lca(root, p, q):
if not root or root is p or root is q:
return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
if left and right:
return root # p and q are on different sides
return left or right # both on one side (or not found)
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* l = lowestCommonAncestor(root->left, p, q);
TreeNode* r = lowestCommonAncestor(root->right, p, q);
if (l && r) return root;
return l ? l : r;
}
For a BST it's simpler: walk down, going left if both are smaller, right if both are larger. For many LCA queries on a big tree, use binary lifting (O(log n) per query after O(n log n) preprocessing).
Paths from the root: prefix sums on trees
Path Sum III (count downward paths summing to k) = prefix sum + hash map along the current root-to-node path, with backtracking to remove the current prefix when returning.
def path_sum(root, k):
count = {0: 1}
def dfs(node, prefix):
if not node:
return 0
prefix += node.val
res = count.get(prefix - k, 0)
count[prefix] = count.get(prefix, 0) + 1
res += dfs(node.left, prefix) + dfs(node.right, prefix)
count[prefix] -= 1 # leave this path
return res
return dfs(root, 0)
Building trees from traversals
Preorder + inorder uniquely define a tree (with distinct values). The first preorder value is the root; its inorder position tells you the left subtree's size.
def build_tree(preorder, inorder):
pos = {v: i for i, v in enumerate(inorder)}
it = iter(preorder)
def build(lo, hi): # inorder range [lo, hi]
if lo > hi:
return None
root = TreeNode(next(it))
mid = pos[root.val]
root.left = build(lo, mid - 1) # must build left first (preorder order)
root.right = build(mid + 1, hi)
return root
return build(0, len(inorder) - 1)
Serialization
class Codec:
def serialize(self, root):
out = []
def dfs(n):
if not n:
out.append("#"); return
out.append(str(n.val)); dfs(n.left); dfs(n.right)
dfs(root)
return ",".join(out)
def deserialize(self, data):
tokens = iter(data.split(","))
def build():
t = next(tokens)
if t == "#":
return None
node = TreeNode(int(t))
node.left = build(); node.right = build()
return node
return build()
Trees as graphs
When you need to move upward or treat the tree as undirected (All Nodes Distance K, Burning Tree), record parent pointers with one DFS, then BFS from the start node over left, right and parent.
Complexity
Every traversal visits each node once: O(n) time. Space is O(h) for recursion — O(log n) if balanced, O(n) if skewed. BFS uses O(w) where w is the max width (up to n/2).
Common mistakes
- Not handling
None/nullptrchildren as the base case. - Confusing height in nodes vs edges (diameter is in edges).
- Using a global/nonlocal variable without resetting it between test cases (class members in LeetCode persist!).
- Returning the global answer instead of the value the parent needs.
- Deep recursion on skewed trees in Python (10⁵ nodes) → raise the limit or go iterative.
Practice problems
Ordered roughly from warm-up to hard. Try each one for 25–40 minutes before peeking at the key idea; if you needed the hint, mark it “review” and redo it in a few days.
Click the box to cycle: solved ✓ → needs review ↺ → not started. Links open LeetCode.