Count Good Nodes in Binary Tree — The Ridge Lookouts

Boss 10: The Ridge Lookouts

Count the information flows you've mastered: answers rising up (Bosses 2-4), two trees in lockstep (5-6), levels sweeping across (8-9). This boss completes the compass: knowledge flowing down, carried in the recursion's arguments, each branch inheriting what its ancestors saw.

Small boss, big pattern. "Pass the path's context downward" is half of backtracking (Dungeon 9 says hello in advance), and it's the natural shape for any question that begins "along the path from the root...".

The story

The park's ridge trail network branches from base camp:

        Base(3)
       /       \
     (1)       (4)
     /         /  \
   (3)       (1)  (5)

Numbers are elevations. The rating rule for a lookout: good if the trail from base camp to it never passed anything strictly taller. You've already seen that view, says the park, if a taller point stood behind you on your own trail.

Rate them all:

• Base(3): nothing before it. Good. (Base camp is always good.)
• (1), left of base: the trail is 3 → 1, and 3 is taller. Not good.
• (3), below that: trail 3 → 1 → 3. Tallest before it: 3. It ties the max, and ties count, nothing is taller. Good.
• (4): trail 3 → 4. Nothing taller before. Good.
• (1), under 4: trail 3 → 4 → 1. The 4 looms. Not good.
• (5): trail 3 → 4 → 5. Nothing taller. Good.

Count: 4.

Notice what each verdict needed: not the whole trail, just one number, the maximum elevation so far on it. The trail's entire history, compressed into a single value that updates as you descend.

The problem, dressed up properly

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

LeetCode 1448. "Greater than", strictly, so equals survive, the tie rule from the story.

The naive attempt

Carry the actual path. At each node, walk the list of ancestors and check for anything taller:

def good_nodes(root):
    count = 0
    def dfs(node, path):
        nonlocal count
        if not node:
            return
        if all(v <= node.val for v in path):
            count += 1
        dfs(node.left, path + [node.val])
        dfs(node.right, path + [node.val])
    dfs(root, [])
    return count

Correct, and doubly wasteful: the all() rescans the ancestry at every node (O(h) per node, O(n·h) total), and path + [node.val] copies the list at every call. The diagnosis writes the cure: the only fact the check uses is the path's maximum. Carry the digest, not the archive.

The weapon: a running maximum, passed at every fork

Each recursive call receives max_so_far, the tallest elevation on the trail above this node. The node's work:

1. Verdict: node.val >= max_so_far → good, count 1, else 0.
2. Update: the max handed to the children is max(max_so_far, node.val).
3. Combine: my subtree's count = my verdict + left's count + right's count.

Two flows in one function, and this is the boss's actual lesson: context flows down through arguments (max_so_far, each branch getting a personalized copy of its own trail's history) while answers flow up through returns (the counts, summed at each fork). Down-and-up in a single pass. Boss 14 runs on exactly this two-way plumbing.

And a lovely detail: no shared state. Each branch's max_so_far is its own; the left trail's giant peaks never contaminate the right trail's verdicts. The call stack does the bookkeeping that the naive version did with copied lists.

Watching it work

dfs(3, max=-∞)   3 ≥ -∞  GOOD   pass max=3 down
├─ dfs(1, max=3)   1 < 3   not good   pass max=3
│   └─ dfs(3, max=3)   3 ≥ 3  GOOD (tie!)   → returns 1
│   → returns 0 + 1 = 1
└─ dfs(4, max=3)   4 ≥ 3  GOOD   pass max=4
    ├─ dfs(1, max=4)   1 < 4   not good  → 0
    └─ dfs(5, max=4)   5 ≥ 4  GOOD  → 1
    → returns 1 + 0 + 1 = 2

total: 1 + 1 + 2 = 4 ✓

The tie at the deep 3: it inherited max=3 from its own ancestor and passed 3 ≥ 3. Strictly-greater blocks, equal survives.

The code

def good_nodes(root: TreeNode) -> int:
    def dfs(node, max_so_far):
        if not node:
            return 0
        good = 1 if node.val >= max_so_far else 0
        new_max = max(max_so_far, node.val)
        return good + dfs(node.left, new_max) + dfs(node.right, new_max)
 
    return dfs(root, float("-inf"))

Seeding with -inf makes the root automatically good with zero special-casing, nothing is taller than negative infinity. (Seeding with root.val also works and reads nicely; just don't seed with 0, elevations can be negative, LeetCode's are as low as -10⁴.)

Gotchas

1. Strict vs non-strict, inverted. Good means nothing greater on the path, so the verdict is node.val >= max_so_far. Writing > demotes every tie, and the deep 3 in the story is your regression test.

2. A global max instead of a passed max. One shared max_so_far mutated in place bleeds the left trail's peaks into the right trail's verdicts. The whole point is per-path context; arguments give each branch its own. (If you must mutate shared state, you must also un-mutate it on the way out, and that un-mutation discipline is literally Dungeon 9's backtracking. Arguments let you skip the ceremony today.)

3. Updating the max before the verdict. new_max first, then compare against it, and every node compares against itself: everything is good, count = n. Verdict against the inherited max, update after.

4. Seeding with 0. Works until the first all-negative tree, then the root (say, -3) fails -3 ≥ 0 and the guaranteed-good root goes uncounted. -inf or root.val, never a magic constant.

Complexity

One visit per lookout, O(1) work each.

Time: O(n). Space: O(h) for the stack, and nothing else, the naive version's path copies are gone.

Boss down. XP gained.

The park prints four telescope icons on the trail map, and the deep lookout that tied its ancestor gets one, the rulebook's tie clause vindicated.

What you walked away with:

• Downward context: pass ancestry through arguments, each branch inheriting a personalized copy
• Compress the path to its sufficient digest, here a single running max
• Down-and-up in one pass: context descends via arguments, counts ascend via returns
• -inf seeding, strict-vs-non-strict discipline, and verdict-before-update ordering

You now hold the exact toolkit for the dungeon's most famous trap. The next boss looks like Boss 7's BST rule plus a quick check, and an entire generation of engineers has flunked it by checking only the children. Two bounds, passed downward, exactly like today's max.

Next up: Boss 11 — The Library Audit. A rare-books library claims its catalog tree is a true BST, and the auditor who checks each shelf against just its immediate neighbors approves a corrupted catalog. Every node must respect an inherited range, narrowing at every turn. Boss 10's pattern, with two numbers riding shotgun instead of one.