Tree DFS: pass state down, return answers up
Recursion on trees where each call returns one fact to its parent and updates one global best on the way.
Diameter of a Binary Tree. Return the number of edges on the longest path between any two nodes. The tree is given in level order, with None for missing children.
Signals that point here
- Anything on a tree: depth, balance, path sums, lowest common ancestor, serialise, validate a BST.
- "The answer at a node depends on the answers of its children" (post-order).
- "Each node needs something from its ancestors" (pre-order: pass it down as a parameter).
The idea
Ask two questions for every tree problem. What does a call return to its parent? Here: the depth of the subtree. What does it update globally? Here: the best left + right seen, because the longest path may bend through any node.
Separating those two quantities is the trick. Returning the diameter itself does not compose; returning depth does, and the diameter is computed alongside.
from collections import deque
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def build(values: list) -> "TreeNode | None":
"""Level-order list with None for gaps, e.g. [1, 2, 3, None, 4]."""
if not values or values[0] is None:
return None
root, i = TreeNode(values[0]), 1
queue = deque([root])
while queue and i < len(values):
node = queue.popleft()
for side in ("left", "right"):
if i < len(values) and values[i] is not None:
setattr(node, side, TreeNode(values[i]))
queue.append(getattr(node, side))
i += 1
return root
def diameter(values: list) -> int:
best = 0
def depth(node) -> int: # returns: height in nodes
nonlocal best
if node is None:
return 0
left, right = depth(node.left), depth(node.right)
best = max(best, left + right) # updates: longest path through node
return 1 + max(left, right)
depth(build(values))
return bestpublic static class TreeDfs
{
public sealed class TreeNode
{
public int Val; public TreeNode? Left, Right;
public TreeNode(int val) => Val = val;
}
public static TreeNode? Build(int?[] values) // level order, null for gaps
{
if (values.Length == 0 || values[0] is null) return null;
var root = new TreeNode(values[0]!.Value);
var queue = new Queue<TreeNode>(new[] { root });
int i = 1;
while (queue.Count > 0 && i < values.Length)
{
var node = queue.Dequeue();
if (i < values.Length && values[i] is int l) { node.Left = new TreeNode(l); queue.Enqueue(node.Left); }
i++;
if (i < values.Length && values[i] is int r) { node.Right = new TreeNode(r); queue.Enqueue(node.Right); }
i++;
}
return root;
}
public static int Diameter(int?[] values)
{
int best = 0;
int Depth(TreeNode? node) // returns: height in nodes
{
if (node is null) return 0;
int left = Depth(node.Left), right = Depth(node.Right);
best = Math.Max(best, left + right); // updates: longest path through node
return 1 + Math.Max(left, right);
}
Depth(Build(values));
return best;
}
}Complexity
O(n) time. O(h) stack space where h is the height: O(log n) balanced, O(n) for a path-shaped tree. Mention that deep trees can overflow the recursion limit (Python's default is 1,000) and an explicit stack fixes it.
Pitfalls interviewers watch for
- Returning the diameter from the recursion instead of the depth.
- Mixing up nodes and edges: depth here counts nodes, the diameter counts edges, and
left + rightis already in edges. - Forgetting
nonlocalin Python, sobestis a new local variable.
Variants worth knowing
- Maximum path sum: return
max(0, best child gain) + val, update withleft + right + val. - Validate a BST: pass
(low, high)bounds down. - Lowest common ancestor: return the node if found in a subtree; the first node with hits on both sides is the answer.
Test it like the interviewer will
diameter([1, 2, 3, 4, 5])returns3diameter([1, 2])returns1diameter([])returns0diameter([1, 2, null, 3, 4, 5, null, null, 6])returns4- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: diameter([1, 2, 3, 4, 5, null, null, 6])
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- Return the maximum root-to-any path sum where values may be negative.
- Check whether a binary tree is height-balanced in one pass.
- Serialise and deserialise a binary tree.
Check yourself
What are the two questions to ask on any tree problem?
What each call returns to its parent, and what it updates globally (if anything).
Why not return the diameter directly?
A parent cannot combine its children's diameters; it can combine their depths.