1448 · Count Good Nodes in Binary Tree

The cleanest statement of sub-variant D: the parameter is the state. maxSoFar flows down the recursion as an argument; nothing flows back up but a count. No fields, no mutable boxes, no second pass.

1 — The problem

A node is good if no node on the path from the root to it has a larger value. Count them. The root is always good, vacuously.

The phrase "on the path from the root to it" is the tell. Whatever a node needs to know is a property of its ancestors, not its descendants — so the information travels downward, which means it is an argument, not a return value.

Direction	Mechanism	In this problem
Down — what my ancestors know	an extra parameter, recomputed at each call	`maxSoFar`, the largest value seen on the way here
Up — what my descendants found	the return value, aggregated	the number of good nodes in this subtree

Both directions are in use here, and keeping them straight is the skill. Sub-variant A uses only the upward channel; sub-variant D adds the downward one. If you find yourself wanting a field to hold maxSoFar, you have collapsed a per-path value into a per-traversal one, and siblings will contaminate each other.

2 — One number, flowing down

Watch the max so far strip. It is not global — when the recursion finishes the left branch and starts the right, the value reverts, because it was never anywhere but on the call stack.

The two 1s in this tree are both rejected, but for different reasons: the left one is compared against 3, the right one against 4. Same value, same verdict, different ancestor evidence — which is exactly why the state cannot be shared between the branches.

2.1 Why `>=` and not `>`

"No node with a greater value" permits ties. A node equal to the running maximum is still good, so the test is >=. Two consequences:

In the visualizer, the deeper 3 is good — it ties the root and is not beaten by it. With > the answer drops to 3 and the sample still looks plausible.
A tree of all-equal values has every node good. That is the fastest test for this off-by-one, and worth running mentally before submitting.

The initial call passes Integer.MIN_VALUE, or equivalently root.val — either makes the root good. Passing 0 is wrong the moment values can be negative.

2.2 Down-flowing state elsewhere in sub-variant D

Problem	What flows down	Transformed how
1448. Good Nodes	`maxSoFar`	`max(maxSoFar, val)` — monotone, never shrinks
129. Sum Root to Leaf	the number built so far	`cur * 10 + val` — and harvested only at leaves
1315. Even-Valued Grandparent	parent and grandparent values	shift by one generation per level
112. Path Sum	the remaining target	`target - val`, tested at leaves

3 — Complexity and edge cases

Time O(n), space O(h). Every node is visited once and does O(1) work; the only extra memory is one int per stack frame.
Single node: 1. The root is good against MIN_VALUE.
Strictly decreasing path: only the root is good — the running maximum is set once and never matched again.
Strictly increasing path: every node is good, and maxSoFar updates at each level.
Negative values: handled, provided the seed is Integer.MIN_VALUE and not 0.
Common bug: holding maxSoFar in a field and restoring it after the recursive calls. It works, it is backtracking, and it is unnecessary — a parameter already gives every path its own copy. Reach for explicit backtracking only when the state is a mutable structure, as in LC 257.

4 — Reference implementation

Java 21Parameter-carried state, matching the visualizer.9 lines

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

private int count(TreeNode nd, int maxSoFar) {
    if (nd == null) return 0;
    int good = nd.val >= maxSoFar ? 1 : 0;   // ties count
    int m = Math.max(maxSoFar, nd.val);        // what my children inherit
    return good + count(nd.left, m) + count(nd.right, m);
}

No field is declared anywhere. That is the mark of a clean sub-variant D solution — if one is needed, the state was not actually per-path.