Count Good Nodes in Binary Tree

1. Problem & Core Objective

A node X is good if no node on the path from the root to X has a value greater than X. Count the good nodes.

      3            3 is good (root always is)
     / \
    1   4          1 is not (3 > 1);  4 is good (4 >= 3)
   /   / \
  3   1   5        3 is GOOD — its path max is 3, and 3 >= 3 (ties count)
                   1 is not (4 > 1);  5 is good (5 >= 4)

Output: 4

Constraints: 1 <= nodes <= 10^5 · -10^4 <= Node.val <= 10^4

What's actually being tested: passing information down the recursion rather than returning it up. Every question so far has combined results from children; this one hands context to them. It's the simplest problem in the section conceptually, and it's here to establish that direction of flow before question 11 needs it.

2. First-Principles Thought Process

Restate the condition

"No node on the root-to-X path exceeds X" is the same as:

X.val >= max(all values on the path from the root to X, excluding X)

Equivalently, X.val >= maxSoFar where maxSoFar is the largest value seen on the way down.

Note it's >=, not >. A node equal to the running maximum is good — nothing on the path is greater than it. Getting this wrong quietly undercounts, and the example above has exactly such a node.

The direction of information flow

Compare with the earlier questions:

Here each node needs to know about its ancestors, not its descendants. That's a parameter, not a return value.

The recursion

count(node, maxSoFar):
    if node is null: return 0
    good = (node.val >= maxSoFar) ? 1 : 0
    newMax = max(maxSoFar, node.val)
    return good + count(left, newMax) + count(right, newMax)

Start with maxSoFar = root.val, so the root is always good — which matches the definition, since its path is just itself.

Why the running max is enough

You don't need the whole path, only its maximum. The condition compares X against every ancestor, and X >= all of them is exactly X >= max of them. Carrying one integer replaces carrying a list.

3. Solution Paths

Approach 1 — Recompute the path for every node (brute force)

public int goodNodes(TreeNode root) {
    return count(root, new ArrayList<>());
}

private int count(TreeNode node, List<Integer> path) {
    if (node == null) return 0;

    int max = Integer.MIN_VALUE;
    for (int v : path) max = Math.max(max, v);      // re-scan the whole path
    int good = (node.val >= max) ? 1 : 0;

    path.add(node.val);
    int total = good + count(node.left, path) + count(node.right, path);
    path.remove(path.size() - 1);                    // backtrack
    return total;
}

• Time O(n · h) · Space O(h)

Counter-questions on this approach

⭐ "What's redundant here?"

The rescan. At every node I loop over the entire path to find its maximum — but that maximum is almost entirely the same as the parent's, differing by at most the parent's own value.

Since the only thing the condition needs is the maximum, I can carry it as a single number and update it in O(1) on the way down. The list buys nothing.

⭐ "How bad is O(n · h)?"

On a degenerate tree, h = n, so 10^5 × 10^5 = 10^10. That's a hard timeout. Even on a balanced tree it's 10^5 × 17, which passes — but the fix is strictly simpler code, so there's no trade.

"Why does the list need the path.remove at the end?"

It's backtracking — the list is shared mutable state across the whole traversal, so the node must undo its own addition before returning, or its sibling's subtree would see it as an ancestor. It's a correct pattern (and central to Backtracking), but here it's solving a problem I shouldn't have created.

Approach 2 — Carry the running maximum down (optimal)

public int goodNodes(TreeNode root) {
    return count(root, Integer.MIN_VALUE);
}

private int count(TreeNode node, int maxSoFar) {
    if (node == null) return 0;

    int good = (node.val >= maxSoFar) ? 1 : 0;
    int newMax = Math.max(maxSoFar, node.val);

    return good + count(node.left, newMax) + count(node.right, newMax);
}

Trace — the example tree [3,1,4,3,null,1,5]:

Total 4 ✓

• Time O(n) · Space O(h) stack

Counter-questions on this approach

⭐ "Why >= rather than >?"

The condition is "no node on the path has a value greater than X". A node equal to the running maximum has no ancestor greater than it, so it qualifies.

The example proves it: the leaf 3 under node 1 has path max 3, and 3 >= 3 makes it good. With a strict > the answer would be 3 instead of 4. It's the kind of off-by-one that passes many tests, so I'd check it against a tie case deliberately.

⭐ "Why start with Integer.MIN_VALUE rather than root.val?"

Either works. MIN_VALUE makes the root trivially good — which is correct, since its path contains only itself — and avoids dereferencing root before the null check. Starting with root.val also works, since root.val >= root.val, but it needs a null guard first.

I use MIN_VALUE because it keeps the function total: it behaves correctly on a null root with no special case.

"Is MIN_VALUE safe given the value range?"

Yes — values are bounded by 10^4, so MIN_VALUE is far below anything real and can never be tied. If values could legitimately be Integer.MIN_VALUE I'd pass long or use a boxed Integer with a null check. Worth verifying rather than assuming, same as the −1 sentinel in question 4.

"Why does this pass information down rather than returning it up?"

Because "good" depends on ancestors, not descendants. A node's children can tell it nothing relevant. That makes the running maximum a parameter, and the count a return value — the two flow in opposite directions in the same function.

That's worth stating, because most tree problems in this section flow only upward, and recognising when you need downward context is the transferable bit.

"Could you do it iteratively?"

Yes — DFS with an explicit stack of (node, maxSoFar) pairs, or BFS with the same pairs in a queue. That avoids 10^5 stack frames on a degenerate tree, which is a real risk here.

Comparison

4. Why the Optimal Wins

The brute force stores the whole path and rescans it at every node. The optimal observes that the condition only asks about the path's maximum, so a single integer, updated in O(1) per level, carries everything needed.

O(n · h) → O(n), and the code gets shorter.

The framing worth keeping:

When a node's answer depends on its ancestors, pass the needed summary down as a parameter. Carry the summary, not the history.

The complement to the upward flow in questions 2, 3 and 4 — and questions 11 and 12 both need this direction too.

5. Java Prerequisites

Downward context as a parameter

int dfs(TreeNode node, int contextFromAncestors) {
    ...
    int updated = combine(contextFromAncestors, node.val);
    return dfs(node.left, updated) + dfs(node.right, updated);
}

Nothing is mutated and nothing is backtracked — each call gets its own copy, which is why no remove is needed.

Sentinel initial values. Integer.MIN_VALUE for a running maximum, MAX_VALUE for a minimum. Confirm the real data can't reach them.

Boolean to int

int good = (node.val >= maxSoFar) ? 1 : 0;

Java has no implicit boolean-to-int conversion.

Stack depth. At n = 10^5, a degenerate tree overflows. An explicit stack of (node, max) pairs is the fix.

6. Interview Communication Guide

Clarifying questions: Is the root always good (yes — its path is only itself)? Is a node equal to the path maximum good (yes — "greater than", not "at least"; this is the off-by-one)? Does the path include the node itself (it doesn't matter, since X >= X)? How deep could the tree be (10^5 means recursion is a real risk)?

The pitch

"The condition is that no ancestor has a larger value, which is the same as saying the node is at least as large as the maximum on its root-to-node path.

The important thing is that this depends on ancestors, not descendants — so unlike depth or diameter, the information flows down the recursion as a parameter rather than up as a return value.

And I don't need the whole path, only its maximum. X >= every ancestor is exactly X >= max of the ancestors, so one integer carries all the context.

So: recurse carrying maxSoFar, count the node if val >= maxSoFar, pass max(maxSoFar, val) to both children, and sum. Start at Integer.MIN_VALUE so the root is automatically good and the function handles a null root with no special case.

I'd be careful with >= rather than >. A node tied with the path maximum is good, because nothing on the path is strictly greater. The given example has exactly that case — a 3 under a 1 beneath a root of 3 — and a strict comparison returns 3 instead of 4.

O(n) time, O(h) stack. At n = 10^5 a degenerate tree would overflow, so I'd switch to an explicit stack of (node, max) pairs if depth were a concern."

Edge cases to volunteer:

Name [3,3]. It's the smallest input that distinguishes >= from >, and it's the only thing that can really go wrong in this problem.

7. Follow-Up Questions — Modified Constraints

⭐ "Count nodes strictly greater than all ancestors."

Change >= to >. The root needs care: with Integer.MIN_VALUE as the seed it would still count, which may or may not be wanted — I'd ask. This is the mirror of the off-by-one above, and it's a good check that the comparison was chosen deliberately.

⭐ "Return the good nodes themselves, not the count."

Collect into a list instead of summing. Identical traversal; the return type changes from int to a list, or you accumulate into a field. Note the return value and the downward parameter remain independent — which is the structural point of this question.

"Find the maximum value along each root-to-leaf path."

The same downward maximum, recorded at leaves instead of compared. One line moves.

"Count nodes whose value exceeds the average of their ancestors."

Carry a running sum and a count downward instead of a maximum, and compare against sum / count. The structure is unchanged, which shows the pattern generalizes to any summarisable ancestor statistic.

"What if you needed the k-th largest ancestor rather than the largest?"

A single integer no longer suffices — you'd carry a bounded structure, like a size-k min-heap of the largest ancestors seen. That's O(log k) per node and O(k) extra space per path. Worth naming the boundary: the running-summary trick works exactly when the needed statistic is incrementally maintainable.

"What if the tree had 10^6 nodes in a chain?"

Recursion overflows. Use an explicit stack of (node, maxSoFar) pairs — same O(n) time, frames moved to the heap. BFS with the same pairs works equally well here, since nothing depends on visiting order.