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.

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

python

▶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

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.

06

Complexity

Time

O(n)

Space

O(h)

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