Count Good Nodes in Binary Tree

Count Good Nodes in Binary Tree is a clean DFS problem that teaches one of the most reusable tree-traversal tricks: carrying a piece of state down the recursion. Here that state is the largest value seen so far on the path from the root.

The slow way first

You could, for every node, walk all the way back up to the root and check whether any ancestor is strictly greater than it. That is O(n) work per node, so O(n²) overall — and it re-walks the same ancestors over and over.

The question to ask: what do I actually need to know to decide if a node is good? Just one number — the maximum value on the path from the root to here. If the current node is at least that maximum, it is good. So instead of looking up, carry that maximum down as I recurse.

The idea: carry maxSoFar down the DFS

Do a single depth-first traversal. Each call receives maxSoFar, the largest value seen on the path so far. A node is good exactly when node.val >= maxSoFar. Then update maxSoFar = max(maxSoFar, node.val) and pass it to both children. Sum up the good counts from each subtree.

The key insight: a node only needs the single best value above it, not the whole ancestor list. Passing that one number down turns an O(n²) check into one O(n) pass.

Walk through it

Step through the animation. The DFS starts at the root with maxSoFar = -inf, so the root is always good. Watch maxSoFar get passed down each edge. When a node meets or beats the running max it turns green (good); when a bigger ancestor sits above it, it turns red (not good). The good counter ticks up to 4.

Pseudocode

dfs(node, maxSoFar):
    if node is None:
        return 0
    good = 1 if node.val >= maxSoFar else 0   # tie counts as good
    maxSoFar = max(maxSoFar, node.val)         # update before recursing
    good += dfs(node.left,  maxSoFar)
    good += dfs(node.right, maxSoFar)
    return good
 
answer = dfs(root, -infinity)

The Python solution

def good_nodes(root):
    def dfs(node, max_so_far):
        if node is None:
            return 0
        good = 1 if node.val >= max_so_far else 0
        max_so_far = max(max_so_far, node.val)
        good += dfs(node.left, max_so_far)
        good += dfs(node.right, max_so_far)
        return good
    return dfs(root, float("-inf"))

• dfs returns the number of good nodes in the subtree rooted at node, given the max_so_far on the path above it.
• The base case node is None returns 0 — an empty subtree has no good nodes.
• Line 5 is the decision: node.val >= max_so_far makes this node good. A tie counts, because the rule only excludes strictly greater ancestors.
• Line 6 updates max_so_far before recursing, so children see the larger of the path max and this node.
• We add the good counts from both children and return the total. The top-level call starts with float("-inf") so the root is always good.

Complexity

The DFS visits every node exactly once for O(n) time. The extra space is O(h) for the recursion stack, where h is the tree height — O(log n) for a balanced tree, O(n) for a degenerate one.

When this pattern shows up

Practice