Binary trees are the most predictable topic in coding interviews. Arrays problems can hide any trick; graph problems sprawl; DP problems mutate endlessly. But tree questions come from a small, stable set of families that hasn’t meaningfully changed in a decade: traverse it, measure it, validate it, or find a path through it.
That predictability is why trees show up in nearly every FAANG loop: interviewers get reliable signal about your recursion skills in a compact 20 minutes. And it’s why trees are the best topic to over-prepare. The return on investment is unusually high.
This post organizes binary tree interview questions into four families, with Python solutions and the one mental model that makes all of them easier. Throughout, we assume the standard node definition:
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
If tree terminology (root, leaf, height, complete vs. balanced) is new, start with Day 13: Introduction to Trees and Day 14: Binary Trees, then come back.
The One Mental Model: Trust the Subtree
Nearly every tree problem yields to the same recursive frame:
Assume the recursive call already solved the problem correctly for the left and right subtrees. Your only job is to combine those two answers with the current node.
Candidates who struggle with trees are almost always trying to mentally trace the whole recursion. Don’t. Ask three questions instead:
- What do I need from each child? (a depth, a boolean, a sum…)
- How do I combine child answers at this node?
- What’s the base case? (almost always
node is None)
Answer those and the code writes itself, usually in under ten lines. This is the same discipline covered in Recursion for Interviews: Think Before You Code. Trees are just recursion’s natural habitat.
Family 1: Traversals (the Vocabulary)
Traversals are rarely the whole question anymore, but they’re the vocabulary every other question is phrased in. You need all four cold.
Depth-first, three flavors: the position of the “visit” relative to the recursive calls is the entire difference:
1def inorder(node, out): # left, node, right
2 if not node:
3 return
4 inorder(node.left, out)
5 out.append(node.val) # visit between children
6 inorder(node.right, out)
7
8# preorder: visit BEFORE children (copying/serializing trees)
9# postorder: visit AFTER children (deleting/evaluating bottom-up)
Breadth-first (level order), the one that needs a queue instead of recursion:
1from collections import deque
2
3def level_order(root):
4 if not root:
5 return []
6 result, queue = [], deque([root])
7 while queue:
8 level = []
9 for _ in range(len(queue)): # exactly one level per pass
10 node = queue.popleft()
11 level.append(node.val)
12 if node.left:
13 queue.append(node.left)
14 if node.right:
15 queue.append(node.right)
16 result.append(level)
17 return result
The for _ in range(len(queue)) idiom (snapshotting the level size before the loop) is the trick that turns plain BFS into level-by-level BFS, and it’s the core of many “medium” questions that are really level order in disguise: right side view (last node per level), zigzag level order (reverse alternate levels), level averages.
All four traversals get a full lesson in Day 16: Tree Traversals, including the iterative DFS variants interviewers sometimes ask as follow-ups.
Interview tip: if the problem says “level,” “nearest,” or “minimum depth,” think BFS. If it says “path,” “depth,” or anything per-subtree, think DFS. Choosing the right traversal and saying why is free signal.
Family 2: Recursive Properties (Measure the Tree)
These are the direct applications of trust-the-subtree: compute something about the whole tree from the same thing about its subtrees.
Maximum depth, the purest example:
1def max_depth(root):
2 if not root:
3 return 0
4 return 1 + max(max_depth(root.left), max_depth(root.right))
Same tree / symmetric tree recurses on pairs of nodes:
1def is_same(p, q):
2 if not p and not q:
3 return True
4 if not p or not q or p.val != q.val:
5 return False
6 return is_same(p.left, q.left) and is_same(p.right, q.right)
(Symmetric Tree is the same function with the recursion mirrored: compare a.left with b.right.)
Balanced tree: the one with a performance trap. The naive solution calls max_depth inside another recursion, giving O(n²). The fix: compute depth and balance in a single pass, using a sentinel to signal failure upward:
1def is_balanced(root):
2 def check(node): # returns height, or -1 if unbalanced
3 if not node:
4 return 0
5 left = check(node.left)
6 if left == -1:
7 return -1
8 right = check(node.right)
9 if right == -1:
10 return -1
11 if abs(left - right) > 1:
12 return -1
13 return 1 + max(left, right)
14 return check(root) != -1
The upgrade from O(n²) to O(n) by returning richer information from the recursion is one of the most transferable tricks in tree interviews. It reappears in balanced-tree checks, diameter, and max path sum. Balance itself matters because it’s what keeps BST operations O(log n); Day 59: Advanced Tree Structures covers the self-balancing trees (AVL, red-black) that real systems use.
Practice: Maximum Depth (104), Same Tree (100), Symmetric Tree (101), Balanced Binary Tree (110), Diameter of Binary Tree (543), Invert Binary Tree (226).
Family 3: BST Problems (Exploit the Invariant)
A binary search tree adds one rule (left subtree < node < right subtree), and every BST question is a test of whether you actually use that rule instead of treating the tree as generic.
Validate BST: the most-asked tree question, with the most-walked-into trap. Checking only node.left.val < node.val < node.right.val is wrong: a grandchild can violate the invariant while every parent-child pair looks fine. The correct approach passes down the valid range:
1def is_valid_bst(root):
2 def valid(node, low, high):
3 if not node:
4 return True
5 if not (low < node.val < high):
6 return False
7 return (valid(node.left, low, node.val) and
8 valid(node.right, node.val, high))
9 return valid(root, float('-inf'), float('inf'))
The elegant alternative: an inorder traversal of a valid BST is strictly increasing, so traverse and check sortedness. Mentioning both approaches is a strong interview move.
Kth smallest element applies the same insight: inorder traversal visits BST values in sorted order, so stop at the kth visit:
1def kth_smallest(root, k):
2 stack, node = [], root
3 while stack or node:
4 while node: # slide left as far as possible
5 stack.append(node)
6 node = node.left
7 node = stack.pop()
8 k -= 1
9 if k == 0:
10 return node.val
11 node = node.right
12 return -1
Search and insert are the warm-ups: each comparison discards half the tree, the same halving logic as binary search on arrays, which is no coincidence. Full implementations, including delete (the fiddly one), are in Day 15: Binary Search Trees.
Practice: Validate BST (98), Kth Smallest in BST (230), Lowest Common Ancestor of BST (235), Insert into BST (701), Convert Sorted Array to BST (108).
Family 4: Path Problems (the Hard Tier)
Path questions are where tree interviews escalate, because “the answer” may live at any node, not just the root.
Lowest common ancestor (LCA), deceptively short, worth rehearsing:
1def lowest_common_ancestor(root, p, q):
2 if not root or root is p or root is q:
3 return root
4 left = lowest_common_ancestor(root.left, p, q)
5 right = lowest_common_ancestor(root.right, p, q)
6 if left and right: # p and q split across subtrees: this is it
7 return root
8 return left or right # both on one side (or not found)
The trust-the-subtree reading: each call answers “did you find p, q, or their LCA down there?” If both sides report a find, the current node is the split point. (For a BST, exploit the invariant instead: walk down from the root until p and q fall on opposite sides.)
Binary tree maximum path sum: the classic hard question, and the full payoff of the return-richer-information trick from Family 2. The subtlety: a node’s contribution to its parent (one downward branch) differs from the best path through it (both branches):
1def max_path_sum(root):
2 best = float('-inf')
3
4 def gain(node):
5 nonlocal best
6 if not node:
7 return 0
8 left = max(gain(node.left), 0) # negative branch? drop it
9 right = max(gain(node.right), 0)
10 best = max(best, node.val + left + right) # path THROUGH node
11 return node.val + max(left, right) # contribution UPWARD
12 gain(root)
13 return best
Two answers per node (one recorded globally, one returned upward) is the pattern behind most hard tree problems (diameter, longest univalue path, house robber III).
Practice: LCA of Binary Tree (236), Path Sum II (113), Binary Tree Maximum Path Sum (124), Diameter (543: do it again with this framing).
Complexity Quick Reference
| Problem family | Time | Space | Why |
|---|---|---|---|
| Any full traversal | O(n) | O(h) | visit every node once; recursion stack is tree height |
| BFS level order | O(n) | O(w) | queue holds one level (w = max width) |
| BST search/insert | O(h) → O(log n) balanced | O(h) | discard half the tree per step |
| Validate BST, LCA, max path sum | O(n) | O(h) | single DFS pass |
The O(h) entries are why interviewers ask “what if the tree is skewed?” Height h is log n for balanced trees but n for a degenerate chain, which is exactly the problem self-balancing trees solve (Day 59).
How to Practice Trees
A sequence where each problem adds one idea:
- Max Depth → Same Tree: pure trust-the-subtree.
- Level Order → Right Side View: the BFS level idiom.
- Balanced Tree → Diameter: returning richer information.
- Validate BST → Kth Smallest: exploiting the BST invariant.
- LCA → Max Path Sum: two-answers-per-node.
That’s roughly how the tree week of our curriculum is sequenced: Day 13 through Day 17 build from terminology to traversals to BSTs to heaps, one idea per day, with recursion already in place from the previous weeks. If you want the whole interview syllabus structured that way, the full 60-day curriculum is free to follow. Create an account to track your progress and pick up where you left off. For the broader picture of which data structures to prioritize, keep the data structures cheat sheet handy.
Related Articles
- Day 14: Binary Trees
- Day 15: Binary Search Trees
- Day 16: Tree Traversals
- Recursion for Interviews: Think Before You Code
- The Data Structures Cheatsheet: Time & Space Complexity for Every Structure You Need
Happy coding, and we’ll see you in the next lesson!