TechPrep
Linked structures, trees and graphsReadLabPracticeCheck

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

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 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

Variants worth knowing

Test it like the interviewer will

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.

  1. Return the maximum root-to-any path sum where values may be negative.
  2. Check whether a binary tree is height-balanced in one pass.
  3. 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.

Saved in this browser.