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
- Find the waste.
max(path)recomputes the maximum of almost the same list at every step; only one value was added. - 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. - Pass it down.
walk(node, tallest)receives the largest value above it. The node is good whennode.val >= tallest; ties count, because the rule says no node is greater. - 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.
- 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
| Approach | Time | Space |
|---|---|---|
| Brute force (scan the path) | O(n · h): each node scans its path, O(n²) for a chain | O(h): the path list and the stack |
| Running maximum (shown code) | O(n): each node visited once, O(1) work | O(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
AttributeErroronroot.val. LeetCode guarantees at least one node; addif not root: return 0if 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.
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.
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?
Exactly the good-nodes pattern with the minimum instead of the maximum: one value passed down, O(1) per node. Parent-only checks miss older ancestors, sorting loses the paths, and storing paths costs O(n · h).
2. Why does the shown solution need only O(1) work per node?
tallest is the maximum of the whole path above, handed down by the parent, so one comparison and one max of two numbers suffice. Every node is still visited.
3. A learner starts the walk with walk(root, 0) instead of walk(root, root.val). Which tree now gets a wrong count?
With a start of 0, a negative root fails node.val >= 0 and is not counted, giving 0. When the root is 0 or more, the start value never matters: the root passes, and the maximum becomes the root's value either way.
Score 60% or more and the lesson is marked complete.