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.

To put this in plain English: you start at the top of the tree. As you walk down a path to a leaf, you keep track of the biggest number you've seen so far. If the node you just stepped on is at least as big as that maximum, it's a "good" node. How many good nodes are there in total?

Constraints to Keep in Mind:

• 1 <= Number of nodes in the tree <= 10^5
• -10^4 <= Node.val <= 10^4
• The tree can be highly unbalanced.

The Brute Force Approach

A naive way to do this without passing state would be to check every node's full path back to the root.

• How it works: For each node in the tree, you somehow traverse from the root down to that node, finding the maximum value on that specific path. Then you check if the node is \ge that maximum.
• Why it's too slow: If you do a fresh path-check for every single node, in a degenerate (line-like) tree of n nodes, the 1st node takes 1 step, the 2nd takes 2 steps, ..., the n-th takes n steps. That's O(n^2) time. Instead, we can just carry the maximum value with us as we walk down, doing it in O(n) time.

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);
}

Code Walkthrough

1. def dfs(node, best_so_far: int) -> int:: We define our recursive helper. It takes the current node and the maximum value seen on the path down to this node (best_so_far). It returns the total number of good nodes in this subtree.
2. if not node: return 0: Base case. An empty tree has 0 good nodes.
3. count = 1 if node.val >= best_so_far else 0: Is the current node good? If its value is \ge the biggest number we've seen, it counts as 1. Otherwise, 0.
4. best_so_far = max(best_so_far, node.val): Update the maximum value. This new maximum is what we will pass down to the children.
5. count += dfs(node.left, best_so_far): Recursively explore the left subtree, adding any good nodes it finds to our total.
6. count += dfs(node.right, best_so_far): Recursively explore the right subtree.
7. return count: Return the grand total for this subtree back up to the caller.
8. return dfs(root, root.val): Kick off the recursion. The root's "best so far" is just its own value.

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

• Time Complexity: O(n). We visit every node in the tree exactly once. At each node, we do O(1) work (a comparison, a max() call, and addition). Thus, total time is strictly linear.
• Space Complexity: O(h) where h is the height of the tree. This is the memory used by the recursion call stack. In the worst case (a degenerate tree), h = n, making space O(n). In a perfectly balanced tree, h = \log n, making space O(\log n). No other extra memory is used.

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.