LeetCode #1448 Medium

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.

treedfs

Open on LeetCode ↗

02

Intuition

The trap is comparing each node only against its immediate PARENT. A node is good when nothing on the ENTIRE root-to-node path beats it, not just the one node directly above -- a node can lose to a grandparent or higher ancestor even while beating its own parent. The fix is to thread the running maximum value seen so far down through the recursion as a parameter, updating it at each step, rather than only looking one level up. A node is good exactly when its value is greater than or equal to that running maximum.

How to spot this pattern

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.

03

Approach

1

Carry the path max as a recursion parameter

dfs(node, maxSoFar) receives the largest value seen anywhere from the root down to node's parent -- not just the parent's own value.

2

Compare against the whole path, not the parent

node is good if node.val >= maxSoFar. If so, increment the count. This correctly handles cases where the parent is small but a grandparent was large.

3

Update the max before recursing into children

Compute newMax = max(maxSoFar, node.val) and pass newMax into both dfs(node.left, newMax) and dfs(node.right, newMax) -- each child sees the true best-so-far, not a stale value.

04

Solution & live demo

▶1class Solution:
▶2    def goodNodes(self, root):
▶3        def dfs(node, maxSoFar):
▶4            if not node:
▶5                return 0
▶6            count = 1 if node.val >= maxSoFar else 0
▶7            newMax = max(maxSoFar, node.val)
▶8            count += dfs(node.left, newMax)   # thread the max down
▶9            count += dfs(node.right, newMax)
▶10            return count
▶11        return dfs(root, float('-inf'))

05

Common pitfalls

Using a shared mutable maximum

✗ Wrong

self.maxSoFar = max(self.maxSoFar, node.val)
dfs(node.left); dfs(node.right)

✓ 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

✗ Wrong

count = 1 if node.val > maxSoFar else 0

✓ Right

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

✗ Wrong

return dfs(root, 0)

✓ Right

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.

06

Edge cases

Root node

Always good -- its path is just itself, so the initial maxSoFar starts at negative infinity (or the root's own value).

Node beats parent but not grandparent

Threading the max (not just parent.val) catches this correctly -- comparing to parent alone would wrongly mark it good.

Strictly increasing path root to leaf

Every node on that path is good, since each exceeds everything before it.

Single-node tree

One good node -- the root.

07

Complexity

Time

O(n)

Space

O(h)

Every node visited once; recursion depth is the tree height h.