Count Good Nodes in a Binary Tree: The Path-Max DFS Pattern
Count Good Nodes in a Binary Tree explained — the O(n) DFS that carries the path maximum down each root-to-node path, with a worked trace and JavaScript.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
A node in a binary tree is good if no node on the path from the root down to it holds a larger value. The root is always good — nothing sits above it. Everything else has to survive a comparison against its own ancestry.
The trap is thinking each node needs to look up at all of its ancestors. It doesn't. One number — the largest value seen so far on the way down — is all the information a node needs to judge itself. Carry that number down the recursion and the whole problem collapses into a single depth-first pass.
That "pass one running value down the tree" move powers a whole family of tree problems, which is why it's worth getting the reasoning exactly right here.
The problem
Given the root of a binary tree, return the number of good nodes. A node X is good if the path from the root to X contains no node with a value greater than X.
Input: root = [3,1,4,3,null,1,5]
3 <- good (root)
/ \
1 4 <- 4 good, 1 not (3 above it)
/ / \
3 1 5 <- left 3 good, right 5 good, 1 not
Output: 4 // good nodes: 3, 3, 4, 5Walk each root-to-node path and ask "is this node at least as big as everything above it?" The root 3 is good by definition. The left child 1 fails — a 3 sits above it. The deeper 3 matches the max of 3 on its path, and equal counts as good. On the right branch, 4 beats the 3 above it, and 5 beats everything, so both are good. The 1 under 4 fails. Four good nodes.
The brute force baseline
The literal reading of the definition: for every node, walk the path from the root down to it and check whether the node ties or beats the maximum on that path.
function goodNodesBrute(root) {
const nodes = [];
(function collect(n) {
if (!n) return;
nodes.push(n);
collect(n.left);
collect(n.right);
})(root);
let ans = 0;
for (const target of nodes) {
// find the path from root to this exact node, tracking the max on it
let maxOnPath = -Infinity;
(function findPath(n) {
if (!n) return false;
const prevMax = maxOnPath;
maxOnPath = Math.max(maxOnPath, n.val);
if (n === target) return true;
if (findPath(n.left) || findPath(n.right)) return true;
maxOnPath = prevMax; // backtrack
return false;
})(root);
if (target.val >= maxOnPath) ans++;
}
return ans;
}This is correct but wasteful. For each of the n nodes, it re-descends from the root to rediscover a path max that a single traversal already computes for free. Each search costs up to O(n), so the whole thing is O(n²) — and it recomputes the exact same partial path maxima over and over. On a degenerate 10⁴-node skewed tree that's a hundred million node visits for an answer one pass could deliver.
The key insight: push the max down, don't pull it up
Every good-node check needs exactly one fact: the maximum value on the path from the root to the current node. The brute force pulls that fact upward by re-walking the path. Flip it — push it downward.
When you're standing at a node during a depth-first traversal, you already know the max on the path that got you there, because your parent handed it to you. You compare, then compute a fresh max (Math.max(maxSoFar, curr.val)) and hand that to your children. The path max is threaded through the recursion as an argument, never recomputed.
Seed the very first call with -Infinity. That guarantees the root's value clears the bar, so the root always counts — exactly matching the definition.
This is the top-down parameter pattern: an accumulator flows down the tree through a recursion argument, and each node makes an O(1) decision the moment it's visited.
The optimal solution
Here is the exact algorithm the visualizer steps through — a DFS closure that carries maxSeenSoFar down and bumps a shared counter:
var goodNodes = function(root) {
let ans = 0;
let traversal = (curr, maxSeenSoFar) => {
if (curr.val >= maxSeenSoFar) {
++ans;
}
let currMax = Math.max(maxSeenSoFar, curr.val);
curr.left && traversal(curr.left, currMax);
curr.right && traversal(curr.right, currMax);
};
traversal(root, -Infinity);
return ans;
};Three details carry the whole thing:
-Infinityseed. The root compares against negative infinity, socurr.val >= maxSeenSoFaris always true for it. No special-casing the root.>=, not>. A node equal to the path max is still good (nothing on the path is greater), so the tie must count. Using>would undercount trees with repeated values.curr.left && traversal(...). The short-circuit skips the recursive call entirely when a child is missing, so there's no separateif (curr === null) returnbase case — you only ever recurse into real nodes.
ans lives in the outer scope and every recursive frame closes over the same variable, so increments from any branch accumulate into one counter.
Walkthrough
Tracing root = [3,1,4,3,null,1,5]. Each row is one traversal(curr, maxSeenSoFar) call, in DFS order (left subtree fully before right). currMax is what gets passed to that node's children.
| Call | curr.val | maxSeenSoFar | val >= max? | ans | currMax passed down |
|---|---|---|---|---|---|
| traversal(3, -Inf) | 3 | -Inf | yes | 1 | max(-Inf, 3) = 3 |
| traversal(1, 3) | 1 | 3 | no | 1 | max(3, 1) = 3 |
| traversal(3, 3) | 3 | 3 | yes | 2 | max(3, 3) = 3 |
| traversal(4, 3) | 4 | 3 | yes | 3 | max(3, 4) = 4 |
| traversal(1, 4) | 1 | 4 | no | 3 | max(4, 1) = 4 |
| traversal(5, 4) | 5 | 4 | yes | 4 | max(4, 5) = 5 |
The deeper 3 (row 3) is the instructive case: 3 >= 3 is true, so it counts even though it only ties the path max — that's the >= at work. The two 1s never count because a bigger ancestor always sits on their path. Final ans = 4.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force (re-walk each path) | O(n²) | O(h) | n nodes × up-to-O(n) path search each |
| DFS carrying path max | O(n) | O(h) | each node visited once, O(1) work; recursion depth = tree height h |
The optimal pass touches every node exactly once and does constant work per node — one comparison, one Math.max, at most two recursive calls. Space is the recursion stack, which reaches the tree's height h: O(log n) for a balanced tree, O(n) for a fully skewed one.
Common mistakes
- Using
>instead of>=. Equal-to-max nodes are good.>silently undercounts any tree with duplicate values — including the LeetCode example, which has two3s. - Seeding with
0instead of-Infinity. Node values can be negative. Seeding at0marks negative-valued roots as not good, breaking the "root is always good" guarantee.-Infinityis the only safe floor. - Returning the max instead of counting. The recursion carries a max downward but the answer is a count. Keep them separate:
currMaxflows into children;ansaccumulates across the whole tree. - Recomputing the path max on the way up. If you find yourself backtracking or re-scanning ancestors, you've slipped back to the O(n²) shape. The point is that the parent already handed you the max — never look upward.
- Forgetting the null-child guard. Without
curr.left && ...(or an explicit null base case), the recursion dereferencescurr.valon a missing child and throws.
Where this pattern shows up next
Threading an accumulator down a DFS is the reusable idea here. These tree problems reuse the same recursion skeleton with a different value flowing through it:
- Maximum Depth of Binary Tree — the bottom-up counterpart, where each node returns a value up instead of receiving one down.
- Maximum Depth of Binary Tree - Top Down — the closest cousin: it pushes the current depth down as a parameter, exactly like the path max here.
- Balanced Binary Tree — combines a downward traversal with an upward height return to check a global property.
- Diameter of Binary Tree — another shared-counter DFS, where each node updates an outer variable during traversal.
You can also step through Count Good Nodes interactively to watch maxSeenSoFar flow down each branch and the good-node counter tick up node by node.
FAQ
Why is the root always a good node?
The path from the root to itself contains only the root, so there is no ancestor that could hold a larger value. By the definition, that makes it good automatically. In code, seeding the first call with -Infinity encodes this: root.val >= -Infinity is always true, so the root is counted without any special case.
Why use >= instead of > in the comparison?
A node is good when no node on its path is strictly greater than it. A node that merely equals the current path maximum still has no larger ancestor, so it qualifies. Using >= counts those ties; using > would wrongly reject them. The LeetCode example itself has a 3 sitting under another 3 that only passes because equality counts.
What is the time and space complexity of Count Good Nodes?
Time is O(n): the DFS visits each of the n nodes exactly once and does constant work per visit — one comparison, one Math.max, and up to two recursive calls. Space is O(h) where h is the tree height, driven by the recursion stack. That's O(log n) for a balanced tree and O(n) in the worst case of a completely skewed tree.
Can I solve this iteratively instead of with recursion?
Yes. Use an explicit stack of [node, maxSoFar] pairs. Pop a pair, run the same node.val >= maxSoFar check, then push each existing child paired with Math.max(maxSoFar, node.val). It carries the identical path-max information without the call stack, which avoids stack-overflow risk on very deep, skewed trees. The recursive version is shorter and is what the visualizer traces.
Does the algorithm work with negative node values?
Yes, as long as you seed the traversal with -Infinity rather than 0. Because -Infinity is smaller than any real value, even a deeply negative root clears the initial bar and is counted, and every path maximum after that is computed from actual node values. Seeding with 0 would break on negative-valued nodes by treating a negative root as not good.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.