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. Equivalently, a node is good if it is greater than or equal to every node on its root-to-node path, itself included. Count the good nodes.

The root is always good: it has no ancestors.

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). Both 1s fail because the root’s 3 exceeds them.

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 fails because both 3s above it are larger.

Example 3

Input:  root = [7]
Output: 1

A single node 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 that threads 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 direct reading of the definition: for every node, walk from the root down to it and verify no ancestor is larger. A DFS that carries the current path as a list does this, but it rescans the ancestors at every node.

# 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


def goodNodes(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 about 10^10 comparisons, so this approach times out.

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

The only thing about the ancestor path that matters is its maximum. Thread that maximum down the recursion in O(1) per step: a node is good iff node.val >= path_max, and each child receives max(path_max, node.val). Every node is then decided with one comparison. (DFS, depth-first search, goes 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


def goodNodes(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. Good nodes are shaded below; each label shows val (path_max):

flowchart TD
    A["3 (3) good"]
    B["1 (3)"]
    C["4 (3) good"]
    D["3 (3) good"]
    E["1 (4)"]
    F["5 (4) good"]
    A --> B
    A --> C
    B --> D
    C --> E
    C --> F
    classDef good fill:#bbf7d0,stroke:#16a34a,color:#000;
    class A,C,D,F good;

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 recursion’s only per-frame state is (node, path_max), so a stack of those pairs replaces the call stack directly. This matters in Python, where a 10^5-deep skewed tree overflows 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


def goodNodes(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: when a node’s status depends on its ancestors, push the relevant summary of the path down as a recursion parameter instead of looking upward (here a running max; elsewhere a running sum, count, or bound). If the summary is O(1), the problem collapses to one DFS in O(n). The same top-down threading solves path-sum problems and BST validation.