Count Good Nodes in Binary Tree

PracticeNeetCode ↗LeetCode ↗

Given a binary tree, a node is "good" if no node on the path from the root down to it has a greater value. Return the total number of good nodes.

Example

Key Pointers

• A node is good exactly when its value is greater than or equal to the maximum value seen on the path from the root down to it.
• Carry that running max downward as you recurse — there's no need to look back up the path.
• The root is always good, since nothing above it can beat it.

Step-by-Step Analysis

1. Define a recursive helper dfs(node, max_so_far).
2. If node is None, return 0.
3. count = 1 if node.val >= max_so_far else 0.
4. new_max = max(max_so_far, node.val); recurse into both children with new_max, adding their counts.
5. Return the total count; call dfs(root, root.val) to start.

Complexity

Time: O(n) — Space: O(h)

Code

def goodNodes(root: TreeNode) -> int:
    def dfs(node: TreeNode | None, max_so_far: int) -> int:
        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) + dfs(node.right, new_max)
        return count

    return dfs(root, root.val)

Code Explanation

How the solution above works, piece by piece.

1. dfs(node, max_so_far) carries the largest value seen on the path from the root down to this node.
2. count = 1 if node.val >= max_so_far: nothing above is bigger, so the node is good. Equal counts as good.
3. new_max includes this node before going deeper.
4. Add the counts from both children and return the total.
5. Start with max_so_far = root.val so the root counts. O(n) time, O(height) stack.

Visual Walkthrough

Running it on root = [3, 1, 4, 3, null, 1, 5]:

Video Explanation

NeetCode — Count Good Nodes in Binary Tree, LeetCode 1448