Count Good Nodes in Binary Tree: DFS with Path Maximum

Given a binary tree, a node X is called "good" if the path from the root to X contains no node with a value greater than X. In other words, X is good when its value is greater than or equal to every ancestor along the path. Return the number of good nodes in the tree.

This is LeetCode 1448: Count Good Nodes in Binary Tree. The core idea is to carry a running maximum down through the DFS, and at each node, check whether the node's value meets or exceeds that maximum.

Why this problem matters

Tree problems that require knowledge about ancestors come up frequently in interviews. The pattern here is simple but powerful: pass information downward through the recursion so that each node knows something about the path above it. In this case, the "something" is the maximum value seen so far.

This is the opposite direction from problems like Binary Tree Maximum Path Sum, where you collect information from children and return it upward. Here, you push state from parent to child. Understanding both directions of information flow in tree DFS is essential for solving a wide range of tree problems.

Once you internalize this "pass the max downward" pattern, you can apply it to many variations: counting nodes that satisfy a condition relative to their ancestors, finding paths where values are monotonically increasing, or checking whether any ancestor has a specific property.

The key insight

You do not need to store the entire path from root to the current node. All you need is a single value: the maximum value seen along the path so far. At each node, compare the node's value to this running maximum. If node.val >= max_so_far, the node is good. Then update the maximum to max(max_so_far, node.val) before recursing into children.

This works because the "good" condition only depends on whether any ancestor is strictly greater. Tracking just the maximum captures all the information you need.

The solution

def good_nodes(root) -> int:
    def dfs(node, max_so_far):
        if not node:
            return 0
        count = 1 if node.val >= max_so_far else 0
        new_max = max(max_so_far, node.val)
        count += dfs(node.left, new_max)
        count += dfs(node.right, new_max)
        return count

    return dfs(root, root.val)

Let's walk through each line:

• dfs(node, max_so_far) takes the current node and the largest value seen on the path from the root down to this node.
• if not node: return 0 is the base case. A null node contributes zero good nodes.
• count = 1 if node.val >= max_so_far else 0 checks whether this node is good. If the node's value is at least as large as every ancestor, it counts as good.
• new_max = max(max_so_far, node.val) updates the running maximum. Even if the current node is not good (its value is smaller), we still pass along the old maximum. If the current node is good (its value is larger or equal), it becomes part of the new maximum.
• We recurse into both children, passing the updated maximum, and sum up the good node counts from both subtrees.
• The initial call uses root.val as the starting maximum, which guarantees the root is always counted as good.

Visual walkthrough

Let's trace the DFS through the tree [3, 1, 4, 3, null, 1, 5]. At each node, we track the max_so_far value being passed down and whether the node qualifies as good.

The key moments are in Steps 2 and 3. When we visit node 1 (left child of root), max_so_far is 3 and 1 < 3, so it is not good. But the maximum stays at 3 (not 1), because the running max only increases. When we then visit its child, node 3, we check 3 >= 3, which passes. On the right side, node 4 updates the max to 4, which means its child node 1 fails the check (1 < 4) while node 5 passes (5 >= 4).

Complexity analysis

Time is O(n). Every node is visited exactly once. At each node, you do O(1) work: one comparison and one max call.

Space is O(h) where h is the height of the tree. This is the depth of the recursion call stack. For a balanced tree, h = log n. For a completely skewed tree (like a linked list), h = n.

The building blocks

1. DFS with accumulated state

def dfs(node, state_from_ancestors):
    if not node:
        return base_value
    # Use state_from_ancestors to make a decision about this node
    result = decide(node, state_from_ancestors)
    # Update the state and pass it to children
    new_state = update(state_from_ancestors, node)
    result += dfs(node.left, new_state)
    result += dfs(node.right, new_state)
    return result

This is the "top-down DFS" pattern where information flows from parent to child. You pass state as a parameter rather than returning it. For this problem, the state is max_so_far. For other problems, it might be the current path sum, the depth, or a set of values seen along the path. The key property is that each child gets its own copy of the state, so the left and right subtrees are independent.

2. Path maximum tracking

# At each node, check against max and update
count = 1 if node.val >= max_so_far else 0
new_max = max(max_so_far, node.val)

The running maximum is a compact summary of the entire ancestor path. Instead of storing a list of all ancestor values and checking each one, you maintain a single number that captures the only thing you care about: the largest value seen so far. This reduces the per-node work from O(depth) to O(1).

Edge cases

• Single node: The root is always good (it has no ancestors). The answer is 1.
• All nodes have the same value: Every node is good because val >= max_so_far is always true when all values are equal. The answer is n.
• Strictly decreasing path (e.g. 5, 4, 3, 2, 1): Only the root is good. Every other node has a value smaller than its parent. The answer is 1.
• Strictly increasing path (e.g. 1, 2, 3, 4, 5): Every node is good because each node's value exceeds all ancestors. The answer is n.
• Negative values: The algorithm works unchanged. A node with value -2 is good if all ancestors are also at most -2.
• Large trees: The O(n) time and O(h) space handle trees with up to 100,000 nodes comfortably.

From understanding to recall

You just traced the DFS, watched the max_so_far value flow from parent to child, and saw how each node checks itself against the running maximum. The logic is clean: pass the max down, compare, update, recurse.

But in an interview, will you remember to initialize max_so_far to root.val instead of 0 or negative infinity? Will you remember to use max(max_so_far, node.val) as the new max, not just node.val? These small details are easy to mix up under pressure.

Spaced repetition turns understanding into automatic recall. You practice writing the solution from scratch at increasing intervals. After a few repetitions, the top-down DFS pattern with accumulated state becomes second nature, and you can apply it to any problem that needs ancestor information passed downward.

Related posts

• Binary Tree Maximum Path Sum - DFS through a tree tracking accumulated values
• Maximum Depth of Binary Tree - The foundational recursive DFS tree traversal
• Path Sum II - DFS with path tracking from root to leaves

The ancestor-tracking pattern shows up in many tree problems beyond this one. Master it here, and you will recognize it instantly in variations.