LeetCode 1448 · Trees

Count Good Nodes in Binary Tree, explained with a picture

A hiker counting viewpoints with no taller peak behind.

MediumTrees
▶ Watch it step by step

The problem

A node X is good if, on the path from the root down to X, no node has a value greater than X. Count the good nodes.

Input:  [3, 1, 4, 3, null, 1, 5]
Output: 4

Picture it

Picture a hiker walking down every trail from the summit. Each node is a viewpoint with an altitude. A viewpoint is “good” if nothing on the way down from the top was higher. The hiker carries a note of the highest point seen so far on this trail and compares it with each viewpoint.

How to recognise it

  • The rule for each node depends on every node above it on the path from the root ("no ancestor is greater").
  • You do not need the whole path, only one summary of it: the largest value so far.
  • That summary can be passed down as an argument in a depth-first search (DFS: follow one branch to the bottom before trying the next), updated at each step.
  • Up to 10^5 nodes, so each node must be handled in O(1).

Start with brute force

Keep the actual path from the root in a list. At each node, scan the whole path to find its maximum and compare.

def good_nodes_brute(root):
    count = 0
    def walk(node, path):
        nonlocal count
        if not node:
            return
        path.append(node.val)
        if node.val >= max(path):      # scans the whole path again
            count += 1
        walk(node.left, path)
        walk(node.right, path)
        path.pop()
    walk(root, [])
    return count

Each node scans up to h values, where h is the height, so time is O(n · h). On a chain of 10^5 nodes that is about 5 × 10^9 comparisons, far too slow. On a balanced tree it is only about n log n.

From brute force to the idea

  1. Find the waste. max(path) recomputes the maximum of almost the same list at every step; only one value was added.
  2. Keep only the summary. The maximum of the path including this node is max(tallest, node.val), computed in O(1) from the parent's maximum.
  3. Pass it down. walk(node, tallest) receives the largest value above it. The node is good when node.val >= tallest; ties count, because the rule says no node is greater.
  4. Add up the answers. Each call returns the number of good nodes in its subtree: its own 0 or 1, plus the left and right counts.
  5. Start with the root's own value. walk(root, root.val) makes the root good, as it should be: nothing is above it.

This is the key idea: pass the running maximum of the path down the DFS, so each node is judged in O(1).

The key idea

DFS carrying the max value on the path; a node is good if its value ≥ that max. O(n).

Python solution

def good_nodes(root):
    def walk(node, tallest):
        if not node:
            return 0
        good = 1 if node.val >= tallest else 0
        tallest = max(tallest, node.val)
        return good + walk(node.left, tallest) + walk(node.right, tallest)
    return walk(root, root.val)

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (scan the path)O(n · h): each node scans its path, O(n²) for a chainO(h): the path list and the stack
Running maximum (shown code)O(n): each node visited once, O(1) workO(h): one stack frame per level, h = n for a chain

Edge cases

  • Single node: returns 1.
  • Equal values ([2, 2, 2]): all 3 are good, because the check is >=.
  • Negative values ([-1, -5, -2]): returns 1; the root is good because the start value is the root's own value, not 0.
  • Empty tree: the shown code raises AttributeError on root.val. LeetCode guarantees at least one node; add if not root: return 0 if you reuse it.
  • Very deep tree: a chain of about 1,000 nodes exceeds Python's default recursion limit (RecursionError), and LeetCode allows 10^5 nodes. An explicit stack of (node, tallest) pairs avoids this.

Common mistakes

  • Using > instead of >=, which never counts the root (it is compared with itself) and misses equal values.
  • Starting the maximum at 0, which wrongly rejects a negative root.
  • Updating a shared variable for the maximum instead of passing it down: a value from one branch then leaks into its sibling branch.
  • Comparing only with the parent instead of with the whole path.
Your turn: largest ancestor difference

Return the largest value of |a − b| where node a is an ancestor of node b (LeetCode 1026). For [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13] the answer is 7 (8 and 1). Describe your approach, then write it if you like.

Compare with our answer

The best partner for a node is either the smallest or the largest value above it, so pass both down. At an empty spot, the path is complete: its largest difference is hi - lo.

def max_ancestor_diff(root):
    def walk(node, lo, hi):
        if not node:
            return hi - lo
        lo, hi = min(lo, node.val), max(hi, node.val)
        return max(walk(node.left, lo, hi), walk(node.right, lo, hi))
    return walk(root, root.val, root.val)

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

A strong answer mentions: passing both a minimum and a maximum, that the best difference on a path is its maximum minus its minimum, and starting both at the root's value.

Check what stuck

1. You must count, in a tree of daily prices, the days that set a new low compared with every earlier day on their path. Which approach fits best?

2. Why does the shown solution need only O(1) work per node?

3. A learner starts the walk with walk(root, 0) instead of walk(root, root.val). Which tree now gets a wrong count?

Score 60% or more and the lesson is marked complete.