4.14.10 — Count Good Nodes in Binary Tree

LeetCode 1448 · Medium

The problem

A node is good if no node on the path from the root down to it holds a larger value. Count the good nodes.

      3
    /   \
   1     4         good: 3 (root), 4, 5, 3
  /     / \
 3     1   5

The root is always good, since its path is just itself.

The pattern

Every problem before this one sent information up the tree — a depth, a sum, a yes or no computed from the children. This one sends information down: each node needs to know the largest value seen on the way to it.

That is the other half of tree recursion, and knowing which direction a problem needs is most of the skill.

• Information flowing down — pass it as an extra argument. Path state, depth, an allowed range.
• Information flowing up — return it. Depths, sums, counts, validity.

Here the maximum so far goes down as a parameter, and the count comes back up as a return value. Many problems use both at once.

The solution

Python

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, best_so_far: int) -> int:
            if not node:
                return 0

            count = 1 if node.val >= best_so_far else 0
            best_so_far = max(best_so_far, node.val)

            count += dfs(node.left, best_so_far)
            count += dfs(node.right, best_so_far)
            return count

        return dfs(root, root.val)

TypeScript

function goodNodes(root: TreeNode): number {
  function dfs(node: TreeNode | null, bestSoFar: number): number {
    if (!node) return 0;

    let count = node.val >= bestSoFar ? 1 : 0;
    bestSoFar = Math.max(bestSoFar, node.val);

    count += dfs(node.left, bestSoFar);
    count += dfs(node.right, bestSoFar);
    return count;
  }

  return dfs(root, root.val);
}

>=, not >. A node equal to the largest so far is still good — no node on its path is larger. Getting this wrong quietly loses nodes in trees with repeated values.

Start with root.val, not with negative infinity. Either works, since the root is trivially at least equal to itself. Using root.val makes the intent clearer.

Each branch gets its own best_so_far. Because it is a parameter rather than a shared variable, the left and right subtrees each receive their own copy and cannot interfere. That is the advantage of passing state down instead of mutating something outside — backtracking is automatic. No undo step is needed, unlike the explicit pop() in 4.8.4, because nothing is shared to begin with.

Trace

For the example tree, walking down each path:

path	maxima seen	good?
3	3	yes
3 → 1	3	no, 1 < 3
3 → 1 → 3	3	yes, 3 ≥ 3
3 → 4	3	yes
3 → 4 → 1	4	no
3 → 4 → 5	4	yes

Four good nodes. Note the second 3 counts only because the comparison is >=.

Complexity

O(n) time, O(h) space.

Where this goes next

Every problem where a value flows down a root-to-node path:

• Path Sum — carry the running total down and check it at each leaf.
• Sum Root to Leaf Numbers — carry the digits built so far.
• Validate Binary Search Tree — carry the allowed (min, max) range down, which is 4.14.11 and the clearest example of the technique.
• Path Sum II — carry the path itself, and here you do need an undo, because a single list is shared to avoid copying at every node.

The rule: decide before writing whether the information flows down or up. Down goes in the parameters, up goes in the return value. Problems needing both do both.

What the interviewer will push on

"Which direction does information flow here?" Down, as a parameter. Say it before you code.

"Why >=?" A node equal to the maximum is still good.

"Why is no undo needed?" Each recursive call gets its own copy of the parameter, so branches cannot interfere.

"When would you need an undo?" When the state is a shared mutable structure, like a path list you are appending to.

One thing to volunteer: name the down-versus-up distinction explicitly. It is the single most useful frame for the whole tree chapter, and it makes the two hard problems later look routine.

Next: 4.14.11 Validate Binary Search Tree — passing a range downward, and the wrong answer nearly everybody gives first.