Binary Tree Interview Questions — return values where candidates drown

A binary tree is a data structure where each node has at most two children, a left and a right. Interview rounds test whether you can walk that shape and return something useful to the parent call. Miss the contract and the code runs locally, fails globally.

Jeff Erickson's Algorithms textbook — free online at jeffe.cs.illinois.edu — splits its DFS material into a dedicated Chapter 6 (DFS). The chapter is the cleanest written defense of one claim: depth-first search on a tree is not a traversal algorithm. It is a return-value contract.

That reframe is the entire interview.

“The recursion is not the hard part. The return value is. Name the helper contract before you type and most tree rounds get calmer.”

Tree rounds mostly fail on one thing: a candidate writes a locally reasonable recursive function, then cannot say what the function returns to its parent. The code runs on tiny cases and fails on the real test. The interviewer reads it as "understood the syntax, did not understand the invariant." That is a weak-hire scorecard.

This post classifies the five tree question families, hands you the academic references that teach the return-value contract, and points at the open-source trees you can read when you want to see the pattern in production.

What the interviewer is listening for

A strong tree answer proves five things:

1. You distinguish a general binary tree from a BST before coding.
2. You pick an order — preorder, inorder, postorder, or BFS — because the question needs that order, not by habit.
3. You can state what each recursive call returns to its parent, in one sentence.
4. You separate path-local state from whole-tree state when the problem needs both.
5. You can say the invariant out loud, not just narrate the code.

Erickson's Chapter 6 makes the same five points in more rigorous language. Sedgewick's Princeton BST lecture and MIT 6.006's Spring 2020 lecture notes — Erik Demaine and Srini Devadas teaching — both drill the same discipline. Read the chapter, watch one lecture, and the "clever" tree solutions stop looking clever. They start looking like somebody named the helper contract before typing.

The return value is the contract

Here is the function shape almost every candidate can write:

PYTHON

Copy

def dfs(node): if not node: return 0 left = dfs(node.left) right = dfs(node.right) return max(left, right) + 1

Here is what most candidates cannot do under pressure: say what dfs(node) means. Is it:

• subtree height
• best downward path
• a boolean for "valid subtree"
• the whole-subtree answer
• a node reference

If you do not name the contract before coding, the classic tree-round bug appears: code that is locally reasonable and globally wrong. The walkccc.me CLRS companion — a public open-source companion to Cormen/Leiserson/Rivest/Stein — walks this distinction problem-by-problem. Read chapter 12 and pay attention to how every BST proof leads with the invariant before the code.

Diagram

Copy source

Rendering diagram...

Each child sends exactly one piece of information upward. The parent combines those return values according to the invariant. The question every tree prompt is really asking: what does the parent need from each child to do its own job?

The five binary-tree families

The taxonomy is more stable than most candidates think. Compare Wikipedia's Tree traversal entry with Sedgewick's Princeton BST section and the NeetCode Advanced Algorithms course — the same five families keep coming back.

Family 1 — Traversal order: choose on purpose, not by habit

Level-order, zigzag, right-side view, average of levels, per-depth grouping.

The first question is not "DFS or BFS?" It is: what does the prompt need me to know at each step?

Diagram

Copy source

Rendering diagram...

• Preorder — process the node before recursing. Building path lists, serializing structure, copying a tree.
• Inorder — BST ordering is the whole point. Validation, k-th smallest, in-order successor.
• Postorder — parent answer needs child answers first. Height, diameter, balanced-check, max path sum.
• BFS — the prompt literally talks about layers or frontiers.

PYTHON

Copy

from collections import deque def level_order(root): if not root: return [] q, out = deque([root]), [] while q: out.append([n.val for n in q]) for _ in range(len(q)): node = q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) return out

Invariant to say out loud: The queue stores the current frontier; each outer iteration consumes exactly one level.

Family 2 — BST questions: the ordering rule is the whole point

A BST is not just a tree you happen to recurse on. It carries a contract:

• left subtree values are strictly smaller
• right subtree values are strictly larger
• the rule holds all the way down

Sedgewick's Princeton BST lecture notes and MIT 6.006's OCW lecture notes hammer the same point: every BST algorithm is a proof about the ordering invariant, not a manipulation of left/right pointers. Wikipedia's BST article gives the formal statement.

The candidate mistake: hearing "tree" and forgetting to ask whether the BST property applies. Say it early: Because this is a BST, inorder traversal produces nodes in sorted order. That one sentence gives away half the solution to most BST prompts.

PYTHON

Copy

def is_valid_bst(root): def dfs(node, low, high): if not node: return True if not (low < node.val < high): return False return dfs(node.left, low, node.val) and dfs(node.right, node.val, high) return dfs(root, float("-inf"), float("inf"))

The invariant is the answer. Each node stays inside the range passed down from all of its ancestors, not just compared against its immediate parent. Miss that and the easy bug passes small examples and blows up on the real test.

Family 3 — Path-state: what travels up vs what stays global

Path Sum I/II, Binary Tree Maximum Path Sum, diameter variants, root-to-leaf collections.

This family is where the return-value contract gets loud. The helper usually needs to return one thing (the best downward contribution) while a different thing (the global best) is tracked outside. NeetCode's Maximum Path Sum walkthrough spells the separation out step by step.

Say the contract before you code: The helper returns the best downward path from this node; I update a global best for any path that bends through this node.

PYTHON

Copy

def max_path_sum(root): best = float("-inf") def dfs(node): nonlocal best if not node: return 0 left = max(dfs(node.left), 0) right = max(dfs(node.right), 0) best = max(best, node.val + left + right) return node.val + max(left, right) dfs(root) return best

This shape shows up in production too. CPython's ast.py — the standard library's AST walker — carries the same split: the recursive visit returns per-subtree information while the NodeVisitor class accumulates global state. React's fiber reconciler does the same when computing effect lists — each fiber returns its local contribution while a global effect chain grows separately. Different domains, same discipline: never conflate the path-local return with the whole-tree accumulator.

Family 4 — Relationship: when two branches meet again

Lowest common ancestor, same-tree, subtree checks, nodes at distance k, cousin checks.

Wikipedia on lowest common ancestor has the formal statement; NeetCode's LCA walkthrough is the interview-format version. These are branch-merging questions — the interviewer is listening for whether you understand when information from two sides has to rejoin.

PYTHON

Copy

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

The return contract is clean:

• return the target node if you found it
• return the LCA if this subtree already knows it
• return None otherwise

Distance-k questions are where strong candidates earn easy points: plain DFS only moves downward, so if the question needs upward moves too, say so out loud and add parent references before the second traversal. That is a deliberate design choice. The interviewer grades vocal reasoning.

Family 5 — Shape: nulls are part of the data

Serialize/deserialize, completeness check, width calculation, build-tree-from-traversals.

These questions are about structure, not values. The failure mode: candidates drop null markers "to simplify," and the resulting stream preserves values but destroys shape. Erickson's Chapter 6 walks through tree reconstruction in the "DFS tree" section and makes absence an explicit part of the data model.

PYTHON

Copy

def serialize(root): vals = [] def dfs(node): if not node: vals.append("#") return vals.append(str(node.val)) dfs(node.left) dfs(node.right) dfs(root) return ",".join(vals)

That "#" marker is the reason reconstruction works. Preorder + null markers uniquely encodes a binary tree; preorder alone does not. Say the invariant: Absence is data. Every missing child is a sentinel, not a thing I get to omit.

Common mistakes that cost easy points

Choosing a traversal by habit

Preorder is not the default because recursion feels comfortable. Start by naming what the parent or the next layer needs, then pick the order that delivers it.

Forgetting to ask whether it is a BST

Some tree questions collapse once ordering is available. Others become wrong if you assume ordering that the prompt never gave. Ask early.

Mixing path-local state with whole-tree state

The classic tree bug. You return one thing when the problem needs two. Or you carry global state when a clean return value would have been enough. The strong answer names both roles explicitly.

Hand-waving the base case

None is part of the recursion contract, not an implementation detail. What does the empty subtree contribute? If you cannot answer that in English, your code is about to drift.

Narrating code instead of stating the invariant

Weaker: Then I recurse left, then I recurse right, then I add them. Stronger: The helper returns the best downward contribution so the parent can combine it with the sibling result.

Interviewers grade the second because it sounds correct before the syntax does.

A talk-track for tree prompts

When you freeze on a tree question, walk this script out loud:

1. General binary tree or BST?
2. What does the current node need from its children or peers?
3. Helper contract, in one sentence.
4. Path-local, subtree-local, or whole-tree answer?
5. Invariant, before the loop or recursion.

Sample applied to Max Path Sum: This is a general binary tree, not a BST, so ordering does not help. The parent needs the best downward contribution from each child, so postorder DFS. My helper returns that contribution; I keep a global best because the optimal path can bend through the current node. That sentence is strong even before the code.

Go deeper — the reading list this post is aggregating

For your next tree round, open these in this order:

• Jeff Erickson, Algorithms — Chapter 6 (DFS) — free textbook, University of Illinois. DFS as return-value contract, not traversal recipe. The single best free treatment online.
• Robert Sedgewick, Princeton Algorithms — Binary Search Trees — canonical BST lecture material. Pair it with the Searching section for full context.
• Erik Demaine + Srini Devadas, MIT 6.006 — Introduction to Algorithms (Spring 2020) — the tree-traversal and BST lectures plus lecture notes. Free on OCW.
• walkccc.me, public CLRS companion — Chapter 12 — open-source problem-by-problem walkthrough of CLRS's BST chapter.
• NeetCode (Navdeep Singh), Advanced Algorithms — Trees and the Max Path Sum / LCA walkthroughs — interview-format problem coverage.
• Wikipedia — Tree traversal, Binary search tree, Lowest common ancestor — reference entries. Useful when you want the formal statement of an algorithm in one page.
• Production open-source — CPython's ast.py for AST visiting; React's fiber reconciler for a large-scale tree that runs in every browser tab. Both illustrate the path-local-vs-global-state split in production code.

Open Erickson's Chapter 6 and one Sedgewick lecture. Skim, then do a problem. Faster than any curated "top N tree questions" list.

A 90-minute binary-tree drill plan

If trees still feel slippery, spend one focused block like this:

1. 15 min — Re-derive preorder, inorder, postorder, and level order from scratch. For each, say what it is good for in one sentence.
2. 20 min — Do one BST problem (e.g., Validate Binary Search Tree). Say the ancestor-range invariant before you touch the keyboard.
3. 20 min — Do one path-state problem (Binary Tree Maximum Path Sum is the canonical one). Force yourself to name what returns upward vs what stays global.
4. 20 min — Do one relationship problem (LCA or distance k).
5. 15 min — Do one shape problem (serialize/deserialize or completeness). Prove you are not dropping null markers.

That block covers the five failure modes:

• wrong traversal
• missing BST invariant
• sloppy helper contract
• weak branch-merging logic
• dishonest null handling

Skip the LeetCode title-memorizing grind. Name the contract, say the invariant, pick the order. That is the whole round.

If you want the adjacent mental model for a traversal surface that extends off the tree, pair this with Graph Interview Questions.