Binary Tree Interview Problems: 12 That Cover Every Pattern

Binary trees show up in roughly 25% of DSA interview rounds. Not because the people writing interview loops particularly love trees. The patterns that solve tree problems keep reappearing everywhere: recursive decomposition, state propagation up and down the call stack, BFS level tracking. Trees are a filter, and they're a good one. These 12 binary tree interview problems cover every major pattern you'll actually face. Most candidates walking in know two or three of them, which is exactly why trees work.

Problem	Difficulty	Pattern taught
LC 104 Maximum Depth	Easy	Base recursion shape
LC 226 Invert Binary Tree	Easy	Pre/post-order swap
LC 101 Symmetric Tree	Easy	Paired DFS
LC 102 Level Order Traversal	Medium	BFS level snapshot
LC 98 Validate BST	Medium	Bounds propagation
LC 199 Right Side View	Medium	First-seen-per-depth DFS
LC 236 LCA	Medium	Dual-signal return
LC 105 Construct from Preorder+Inorder	Medium	Tree reconstruction
LC 222 Count Complete Tree Nodes	Medium	Complete tree shortcut
LC 124 Max Path Sum	Hard	Dual-return with global max
LC 297 Serialize and Deserialize	Hard	Preorder encoding
LC 968 Binary Tree Cameras	Hard	Greedy postorder state machine

Foundation: Three Problems That Install the Mental Model

1. Maximum Depth of Binary Tree (LC 104, Easy)

Every recursive tree function has the same skeleton. Handle the null base case, recurse left, recurse right, combine. The question to ask at every node is: what do I need to return to my parent? Here the answer is depth.

def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

That's it. Every harder tree problem just changes what "return to my parent" means. Get this mental model wrong and the rest of the list is guesswork.

2. Invert Binary Tree (LC 226, Easy)

Famous for one reason: the creator of Homebrew, the package manager sitting on your Mac right now, got rejected at Google partly because he couldn't solve this on a whiteboard. He tweeted about it. The post went viral. The tech industry had a collective moment. The problem is three lines.

def invertTree(root):
    if not root:
        return None
    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

You can swap first then recurse (preorder) or recurse first then swap (postorder). Both work. Pick whichever you can reconstruct from memory at 10am under pressure. The lesson: recursive calls handle the subtrees for free. You only have to define each node's local responsibility.

3. Symmetric Tree (LC 101, Easy)

The paired DFS pattern. Instead of passing one node down the recursion, you pass two and compare them simultaneously.

def isMirror(left, right):
    if not left and not right: return True
    if not left or not right: return False
    return (left.val == right.val and
            isMirror(left.left, right.right) and
            isMirror(left.right, right.left))

Left outer mirrors right outer; left inner mirrors right inner. This same paired DFS structure solves LC 100 Same Tree and LC 572 Subtree of Another Tree. Learn the template once, apply it to all three.

Core Patterns: Six Problems Every Interview Tests

4. Binary Tree Level Order Traversal (LC 102, Medium)

Standard BFS gives you a flat stream of nodes with no record of which level they belong to. The fix is a snapshot: measure the queue length at the start of each iteration and process exactly that many nodes before moving to the next level.

while queue:
    level = []
    for _ in range(len(queue)):   # snapshot: this many nodes are at current level
        node = queue.popleft()
        level.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    result.append(level)

This for-loop-inside-BFS idiom shows up unchanged in LC 199, LC 515, LC 637, LC 116, and a dozen more. Learn the shape. For a deeper look at when BFS beats DFS on trees, see BFS vs DFS: One Question Decides It Every Time.

5. Validate Binary Search Tree (LC 98, Medium)

The #1 BST mistake in interviews: checking only that left.val < root.val < right.val at each node. This misses violations deep in the tree. A value can satisfy its immediate parent's constraint but violate a grandparent's.

Every competent interviewer has watched this mistake hundreds of times. They have a counterexample ready. They are waiting for you to write the naive check so they can hand it to you.

The fix: pass bounds down.

def validate(node, lo, hi):
    if not node: return True
    if not (lo < node.val < hi): return False
    return (validate(node.left, lo, node.val) and
            validate(node.right, node.val, hi))

Start with validate(root, -inf, inf). Every left turn tightens the upper bound; every right turn tightens the lower. Have the bounds version ready before the counterexample arrives. See The Binary Search Tree: One Invariant, Every Operation for why BST invariants must hold globally, not locally.

6. Binary Tree Right Side View (LC 199, Medium)

Two solutions. BFS: take the last element of each level. DFS: visit right before left, record the first node seen at each new depth.

def dfs(node, depth, result):
    if not node: return
    if depth == len(result):
        result.append(node.val)   # first node at this depth when going right-first
    dfs(node.right, depth + 1, result)
    dfs(node.left, depth + 1, result)

depth == len(result) fires exactly once per depth, because right-first DFS hits the rightmost node first. BFS is not always required for "level" questions. DFS is often cleaner and uses O(h) space instead of O(w).

7. Lowest Common Ancestor of a Binary Tree (LC 236, Medium)

The return value does double duty. If the current node is p or q, return it. Otherwise return whichever non-null value came back from the children. If both children return non-null, the current node is the LCA.

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    return root if left and right else left or right

A non-null return doesn't always mean "I found the LCA." It might mean "I found p" or "I found q." The caller interprets based on what comes back from both sides. This dual-signal-return trick generalizes to any problem where you need to propagate multiple pieces of information up the stack at once.

8. Construct Binary Tree from Preorder and Inorder Traversal (LC 105, Medium)

Preorder gives you the root. Inorder tells you how many nodes are in the left subtree: everything to the left of the root's position in inorder. Recurse into each partition.

Naive approach rebuilds inorder slices at every level: O(n²). Fast approach: precompute a hashmap from value to inorder index.

idx = {val: i for i, val in enumerate(inorder)}

def build(pre_start, in_start, in_end):
    if in_start > in_end: return None
    root_val = preorder[pre_start]
    root = TreeNode(root_val)
    mid = idx[root_val]
    left_size = mid - in_start
    root.left = build(pre_start + 1, in_start, mid - 1)
    root.right = build(pre_start + left_size + 1, mid + 1, in_end)
    return root

left_size = mid - in_start is the key calculation. It tells you exactly how many preorder elements belong to the left subtree, letting you correctly offset into the preorder array for the right subtree. See Binary Tree Traversal: The Node, the Stack, and the Four Traversals for why preorder with null markers uniquely identifies a tree but inorder alone does not.

9. Count Complete Tree Nodes (LC 222, Medium)

Every solution I see in interviews is O(n). Which is technically correct. It also completely ignores the constraint that makes this problem interesting.

At any node, measure the leftmost depth and rightmost depth. If they're equal, the subtree is a perfect binary tree: count is 2^h - 1, computable in O(1). If they differ, recurse into both subtrees.

def countNodes(root):
    if not root: return 0
    left_h = right_h = 0
    left, right = root, root
    while left: left_h += 1; left = left.left
    while right: right_h += 1; right = right.right
    if left_h == right_h:
        return (1 << left_h) - 1
    return 1 + countNodes(root.left) + countNodes(root.right)

The O(log²n) bound comes from O(log n) height comparisons at O(log n) levels before hitting a perfect subtree. Interviewers who ask this problem expect you to recognize the shortcut. O(n) is a no-hire signal.

Hard Patterns: Three That Push the Bar

The difficulty jump here is real. All three problems test the same underlying skill: holding two ideas in your head at the same time. What does the recursion return to its parent, and what does it update as a side effect along the way? These are separate concerns, and conflating them is where most people get stuck.

10. Binary Tree Maximum Path Sum (LC 124, Hard)

The hardest part is seeing why you can't return the answer you need to your parent.

A path can go up through one child, through the current node, and down through the other child. But if you return that full path up, the parent can't extend it without branching, which creates an invalid path.

The fix is the dual-return trick: the function returns single-branch gain upward, but updates a global maximum considering both branches joined at the current node.

max_sum = [float('-inf')]

def gain(node):
    if not node: return 0
    left_gain = max(gain(node.left), 0)    # discard negative branches
    right_gain = max(gain(node.right), 0)
    max_sum[0] = max(max_sum[0], node.val + left_gain + right_gain)
    return node.val + max(left_gain, right_gain)   # single branch up

This same dual-return pattern solves LC 543 Diameter of Binary Tree and any problem asking for a global property computed over paths. See DFS Pattern Recognition: Every Problem Leaves the Same Five Clues for the general form.

11. Serialize and Deserialize Binary Tree (LC 297, Hard)

What is the minimum information needed to reconstruct a tree? Preorder traversal with explicit null markers works. Inorder alone does not (you can't determine the root without additional context).

Serialization writes preorder DFS with "null" for missing nodes. Deserialization consumes from the same sequence using an iterator, so each recursive call takes exactly the values it needs.

def serialize(root):
    if not root: return "null"
    return f"{root.val},{serialize(root.left)},{serialize(root.right)}"

def deserialize(data):
    vals = iter(data.split(","))
    def build():
        val = next(vals)
        if val == "null": return None
        node = TreeNode(int(val))
        node.left = build()
        node.right = build()
        return node
    return build()

The iterator makes deserialization stateless: no index to track, no off-by-one to manage. This is the cleanest implementation and the one that reads well under pressure. LC 297 appears at Google, Meta, and Amazon onsite rounds regularly.

12. Binary Tree Cameras (LC 968, Hard)

The hardest problem on this list. The greedy insight: never place a camera on a leaf. A leaf's parent covers the leaf and is itself covered by grandparent cameras, so pushing cameras up maximizes coverage per camera.

Process bottom-up (postorder) with three states: 0 means uncovered, 1 means covered without a camera, 2 means has a camera.

cameras = [0]

def dfs(node):
    if not node: return 1   # null nodes count as already covered
    left, right = dfs(node.left), dfs(node.right)
    if left == 0 or right == 0:
        cameras[0] += 1
        return 2            # must place camera here to cover uncovered child
    if left == 2 or right == 2:
        return 1            # this node is covered by a child's camera
    return 0                # both children covered, but not this node yet

if dfs(root) == 0:
    cameras[0] += 1         # root itself is uncovered

After the DFS completes, check whether the root ended up uncovered and add one camera. The null-returns-1 trick is what keeps leaves from being forced to carry cameras: since null "children" are already covered, a real leaf returns 0, signaling to its parent to place a camera there instead.

Binary Tree Interview Problems: The Short Version

The dual-return trick (return single-branch up, update global with full path) is the signature of hard tree problems. It shows up in LC 124, LC 543, and LC 968.
The #1 BST validation bug is checking only immediate neighbors. Pass bounds.
LC 102's level-snapshot for-loop applies unchanged to a dozen BFS tree problems.
For any complete binary tree, always ask whether you can exploit completeness before defaulting to O(n).

If you can explain each solution out loud without looking at the code, you're ready for tree rounds at most companies. Stumble on the explanation and that's your gap, not the code. Practice these under timed voice conditions on SpaceComplexity: knowing the solution and narrating it under pressure are two different skills.