Introduction to Tree Depth Pattern

Tree Depth / Height Pattern

The depth/height pattern solves max-depth, min-depth, balanced-tree, and diameter-family problems with one idea: every node returns a number describing its subtree (height), and optionally updates a global side-effect (diameter, balance flag). Depth is measured from the root down; height is measured from a node down to a leaf — same recurrence shape, opposite direction.

Recognize the pattern

• Problem says maximum/minimum depth, height, balanced, diameter, or "longest path".
• Answer at a node is a function of left and right subtree heights.
• Interview follow-up: "what if the tree is skewed?" (stack space) or "edges vs nodes?" (off-by-one).

Complexity, derived

Visit each of n nodes once doing O(1) work after children return → Θ(n) time. Recursion stack holds the active root→node path → O(h) space (Θ(log n) balanced, Θ(n) skewed). BFS level-count for max depth is also Θ(n) time with O(w) queue space.

// nodes convention (LeetCode maxDepth):
height(null) = 0
height(u) = 1 + max(height(u.left), height(u.right))

// edges convention (CLRS-style):
height(null) = -1
height(leaf) = 0
height(u) = 1 + max(height(u.left), height(u.right))

Worked example

Tree: 1 → (2 → (4, 5), 3). Nodes convention: height(4)=height(5)=height(3)=1; height(2)=2; height(1)=3. Edges convention: leaves 0, node 2 height 1, root height 2.

When to use / when not

Use bottom-up height DFS for max depth, balanced check (return −1 sentinel), diameter (global max of hL+hR). Prefer BFS for minimum depth (first leaf). Not for per-level aggregates (use level-order BFS) or root→leaf path enumeration (carry state downward).

The single-pass discipline (why not O(n²)). The naive "is-balanced" solution computes height(node) from scratch at every node and then compares — but each height call is itself O(n), so recomputing it at all n nodes is O(n²). The correct pattern returns the height and the balance verdict together in one post-order pass: a node returns its height, or a sentinel (e.g. −1) the moment any subtree is unbalanced, short-circuiting the rest. One traversal, O(n). The same fold powers diameter: each node contributes a candidate hL + hR to a global maximum while returning 1 + max(hL, hR) upward.

Diameter is not max depth. Max depth is the longest root→leaf path; the diameter is the longest path between any two nodes and need not pass through the root. That is why diameter is tracked as a global side-effect (best hL + hR seen anywhere), not read off the root's return value.