Count Good Nodes in Binary Tree
A node in a binary tree is good if no node on the path from the root to it has a value greater than it. Count the good nodes.
- The number of nodes in the binary tree is in the range [1, 10^5].
- Each node's value is between [-10^4, 10^4].
Intuition
Count good nodes in binary tree counts nodes where no value on the path from the root is greater. The trap is comparing each node only against its parent, and it is worth seeing exactly why that fails.
A node can beat its parent while losing to a grandparent. Take root 10, left child 3, and that node's child 7. The value 7 beats its parent 3, so a parent-only check calls it good — but 10 sits above it on the path, so it is not:
- A node is good when nothing on the entire root-to-node path exceeds it, not just the one node directly above.
The fix is to carry the maximum seen so far along the path down the recursion, rather than recomputing it or looking upward. Each call receives the largest value from the root down to its parent, compares against it, and passes an updated maximum to its own children.
That parameter is the whole solution. It compresses the entire path history into one number, so no ancestor list or upward traversal is needed.
The root is always good — nothing precedes it — which falls out naturally by seeding the recursion with negative infinity, or with the root's own value.
The comparison is node.val >= maxSoFar, not strictly greater. A node equal to the path maximum still qualifies, since the condition is that nothing is greater than it. Using > silently undercounts on trees with repeated values.
To count good nodes in binary tree, thread the running maximum down through the recursion. Each node compares against the largest value on its root-to-here path, and passes the updated maximum to its children. Top-down state passing is the counterpart to postorder's bottom-up returns.
Approach
Before reading on: price up what plain recursion costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(h) space.
Reject the parent-only comparison
A node can beat its parent while losing to a grandparent — root 10, child 3, grandchild 7. The check must cover the whole path, and this counterexample is worth carrying.
Carry the path maximum down
dfs(node, maxSoFar) receives the largest value from the root to this node's parent. That single number compresses the entire path history, so no ancestor list or upward walk is needed.
Use a non-strict comparison
A node is good when node.val >= maxSoFar. Equal to the path maximum still qualifies, since the rule is that nothing is greater. Using > undercounts on trees with repeated values.
Update the maximum before recursing
Compute newMax = max(maxSoFar, node.val) and pass it into both children. Updating after the recursive calls would let siblings see a stale path maximum.
Seed so the root always counts
Start with negative infinity, or with the root's own value. The root is good by definition — nothing precedes it on its path — and the seeding makes that fall out rather than needing a special case.
Cost of the traversal
Every node is visited once with O(1) work, giving O(n) time. Space is O(h) for the recursion stack — O(log n) balanced, O(n) on a skewed tree.
Solution & live demo
Common pitfalls
Using a shared mutable maximum
self.maxSoFar = max(self.maxSoFar, node.val) dfs(node.left); dfs(node.right)
newMax = max(maxSoFar, node.val) count += dfs(node.left, newMax)
A single field leaks the left subtree's maximum into the right subtree, where those nodes aren't ancestors. Passing the value as a parameter gives each branch its own path history automatically.
Using strict greater-than
count = 1 if node.val > maxSoFar else 0
count = 1 if node.val >= maxSoFar else 0
A node equal to the path maximum still has nothing greater above it, so it qualifies. Strict comparison also fails the root against itself if the initial maximum is the root's own value.
Seeding with zero
return dfs(root, 0)
return dfs(root, float('-inf'))Node values can be negative, so a zero seed disqualifies every negative root. Negative infinity guarantees the root always counts, which it must.
Edge cases
Always good -- its path is just itself, so the initial maxSoFar starts at negative infinity (or the root's own value).
Threading the max (not just parent.val) catches this correctly -- comparing to parent alone would wrongly mark it good.
Every node on that path is good, since each exceeds everything before it.
One good node -- the root.