templates · Trees

Tree DFS that carries info (bottom-up and top-down)

  • The answer for a node needs answers from its children: height, diameter, balanced, max path sum
  • The answer for a node needs something from its path above: max so far, running sum, valid range
  • "For every node…" or "the longest path anywhere in the tree"

Tree DFS (bottom-up)Tree DFS (top-down)

the one rule

The invariant

Bottom-up: height(node) returns the true height of node's subtree. Top-down: maxSoFar is the largest value on the path from the root down to (not including) node.

write it from memory

The template

bottom-up: return info, update the best

javajava.util.*
/** Bottom-up: each call RETURNS info about its subtree (height) and updates the best answer (diameter). */static int diameter(TreeNode root) {    int[] best = {0};                                     // the answer, shared by every call    height(root, best);    return best[0];} static int height(TreeNode node, int[] best) {    if (node == null) return 0;                           // info for an empty subtree    int left = height(node.left, best);                   // ask the children first    int right = height(node.right, best);    best[0] = Math.max(best[0], left + right);            // longest path that bends at this node    return 1 + Math.max(left, right);                     // info the parent needs}

Two different things: the value you return (what the parent needs) and the value you record (the answer). Mixing them is the classic diameter mistake.

fill in the blanks — only these lines change per problem

  1. line 9What an empty subtree reports: 0 for height, true for balanced, or a sentinel like -1 meaning "already broken".
  2. line 12How this node improves the global answer, e.g. left + right (diameter) or node.val + left + right (max path sum).
  3. line 13What the parent needs from this subtree. Often different from the answer you record.

top-down: pass info down

javajava.util.*
/** Top-down: each call RECEIVES info from above (the max on the path so far). Counts "good" nodes. */static int goodNodes(TreeNode root) {    return count(root, Integer.MIN_VALUE);                // what the root receives} static int count(TreeNode node, int maxSoFar) {    if (node == null) return 0;    int good = node.val >= maxSoFar ? 1 : 0;              // decide using what came from above    int next = Math.max(maxSoFar, node.val);              // what to pass down    return good + count(node.left, next) + count(node.right, next);}

The info travels as a parameter. Each child gets its own copy, so there is nothing to undo.

fill in the blanks — only these lines change per problem

  1. line 8The decision at this node using the info from above.
  2. line 9The new info for the children: a new max, a running sum, or a tighter (low, high) range.

complexity

What it costs

time O(n)
Each node is visited once and does O(1) work with its children's answers.
space O(h)
The recursion goes as deep as the tree: about log₂ n when balanced, up to n when skewed.

watch out

Common bugs

  • Returning the diameter instead of the height. The parent needs the height to build longer paths.
  • Keeping the best answer in a local int. Java passes it by value; use a field or an int[] best.
  • Calling a separate height() inside every node. That is O(n²); return the height from the same DFS.

use it

Practise it on

learn it properly