Count Good Nodes in Binary Tree

Problem in plain words

Walk from the root down to some node X. If no node on that walk (before X) has a value strictly larger than X, then X is called good. Count the good nodes in the tree. The root is always good, because nothing comes before it.

Example: root 5, left child 2, right child 7, and 7 has a left child 6. The good nodes are 5 (root), 7 (7 ≥ 5) — 2 is not good (5 > 2) and 6 is not good (7 > 6). The answer is 2.

Intuition

Whether X is good depends only on one number: the maximum value along the path from the root to X's parent. So pass that maximum down as you traverse. At each node, compare its value with the running maximum, then update the maximum before visiting the children. This is a top-down (pre-order) DFS where state flows from parent to child.

Approach

1. Start a DFS at the root with best = root.val.
2. At each node, if node.val >= best, count it as good.
3. Update best = max(best, node.val).
4. Recurse into the left and right children with the updated best.
5. Return the total count.

Dry run

Two nodes are good, so the answer is 2.

Java solution

class Solution {
    public int goodNodes(TreeNode root) {
        return count(root, root.val);
    }

    private int count(TreeNode node, int best) {
        if (node == null) {
            return 0;
        }
        int good = node.val >= best ? 1 : 0;
        int nextBest = Math.max(best, node.val);
        return good + count(node.left, nextBest) + count(node.right, nextBest);
    }
}

Python solution

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

Complexity

Edge cases and common mistakes

• Using `>` instead of `>=` — a node equal to the path maximum is still good. Strict comparison undercounts.
• Sharing one global maximum — the maximum must be per path. Pass it as a parameter so the left and right branches do not affect each other.
• Initialising the maximum to 0 — values can be negative. Start from root.val (or negative infinity).
• Deep trees in Python — with up to 10^5 nodes a recursive solution can hit the recursion limit, which is why the Python version uses an explicit stack.