Count Good Nodes in Binary Tree

Problem

Given the root of a binary tree, call a node good if no node on the path from the root down to it has a value strictly greater than its own value (i.e., the node is greater than or equal to every ancestor on its root path, itself included). Count the good nodes.

The root is always good — there’s nothing above it to beat it.

Examples

Example 1

Input:  root = [3, 1, 4, 3, null, 1, 5]

            3
          /   \
         1     4
        /     / \
       3     1   5

Output: 4

Good nodes: 3 (root), 4 (path max so far is 3), 5 (path max 4), and the leaf 3 (path 3→1→3, max 3, and 3 >= 3). The 1s are beaten by the root’s 3.

Example 2

Input:  root = [3, 3, null, 4, 2]

            3
           /
          3
         / \
        4   2
Output: 3

Good: root 3, the second 3 (ties count), and 4. The 2 loses to the 3s above it.

Example 3

Input:  root = [7]
Output: 1

A lone root is always good.

Constraints

• Number of nodes is in [1, 10^5].
• -10^4 <= Node.val <= 10^4
• Expected complexity: O(n) time — a single traversal; O(h) extra space.

Think about it first

TL;DR

DFS threading the running path maximum down the tree — O(n) time, O(h) space.

Approach 1 — Brute force: check the full ancestor path per node

The naive reading of the definition: for every node, walk from the root down to it and verify no ancestor is larger. Collecting each node’s ancestor list via a DFS that copies the path works, but re-examines ancestors over and over.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import List, Optional


class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        good = 0

        def dfs(node: Optional[TreeNode], path: List[int]) -> None:
            nonlocal good
            if not node:
                return
            if all(v <= node.val for v in path):   # rescan whole path
                good += 1
            path.append(node.val)
            dfs(node.left, path)
            dfs(node.right, path)
            path.pop()

        dfs(root, [])
        return good

Complexity: O(n * h) time — every node rescans its O(h) path, which is O(n^2) on a skewed tree; O(h) space. At n = 10^5 a degenerate chain means ~10^10 comparisons — this is what kills it.

Approach 2 — DFS carrying the path maximum (recursive, canonical)

The insight: the whole ancestor path is irrelevant except for its maximum. That maximum can be threaded down the recursion in O(1) per step: a node is good iff node.val >= path_max, and the child’s path_max is max(path_max, node.val). Each node is then decided with one comparison. (DFS — depth-first search — is the classical traversal: go deep along one branch before backtracking.)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node: Optional[TreeNode], path_max: int) -> int:
            if not node:
                return 0
            good = 1 if node.val >= path_max else 0
            new_max = max(path_max, node.val)
            return good + dfs(node.left, new_max) + dfs(node.right, new_max)

        return dfs(root, root.val)

Walkthrough on Example 1 ([3, 1, 4, 3, null, 1, 5]):

Total good = 4, matching the expected output.

Complexity: O(n) time — one visit and one comparison per node; O(h) recursion stack (h up to n on a skewed tree).

Approach 3 — Iterative DFS with an explicit stack

The insight: the recursion’s only per-frame state is (node, path_max), so a stack of those pairs replaces the call stack verbatim — useful in Python where a 10^5-deep skewed tree would overflow the default recursion limit.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        good = 0
        stack = [(root, root.val)]
        while stack:
            node, path_max = stack.pop()
            if node.val >= path_max:
                good += 1
            new_max = max(path_max, node.val)
            if node.right:
                stack.append((node.right, new_max))
            if node.left:
                stack.append((node.left, new_max))
        return good

Walkthrough on Example 2 ([3, 3, null, 4, 2]): pop (3, 3) → good, push (3, 3); pop (3, 3) → good (tie), push (2, 3), (4, 3); pop (4, 3) → good, new_max = 4, no children; pop (2, 3) → not good. Count = 3.

Complexity: O(n) time, O(h) stack space (worst case O(n)); visit order differs from the recursion but the count is order-independent.

Common pitfalls

• Using strict > instead of >= — ties with the path maximum are good (Example 2’s second 3).
• Seeding the traversal with path_max = 0 or -inf carelessly: values can be negative, so seed with root.val or float("-inf"), never 0.
• Updating the maximum before the goodness test — the node competes against ancestors only, but note node.val >= max(path_max, node.val) happens to give the same answer; the real bug is passing the old max to children.
• Comparing against the parent’s value instead of the running maximum of the whole path.

Pattern takeaway

This is the “root-to-node path property” template: whenever a node’s status depends on its ancestors, don’t look up — push the relevant summary of the path down as a recursion parameter (here a running max; elsewhere a running sum, count, or bound). If the summary is O(1), the whole problem collapses to one DFS in O(n). The same top-down threading solves path-sum problems and BST validation.