Problem overview
The method goodNodes(root) receives the root of a binary tree with at least one node and returns how many nodes are good. A node is good when no node on the path from the root down to it has a greater value. A node equal to the largest value above it is still good, and the root is always good because nothing is above it. The lesson provides the node type: a TreeNode with val, left and right, where a missing child is null.
For the tree [3, 1, 4, 3, null, 1, 5] in level order, the answer is 4: the root 3, the 4, the 5 below it, and the 3 at the bottom left, whose path 3, 1, 3 has nothing greater than 3. The 1 under the root is not good because 3 is above it, and neither is the 1 under the 4. For [3, 3, null, 4, 2] the answer is 3: the root, the 3 under it (an equal value is not greater) and the 4. The 2 is not good, since its path contains a 3. A single node, [1], gives 1.
The statement asks for O(n) time, visiting each node once.
Approach: carry the largest value down the path
The direct way walks back up from every node to the root, checking each value on the path. For a tree h levels deep that costs up to O(n · h).
A better way notices that a node only needs one fact about its ancestors: the largest value among them. If the node's value is at least that, nothing above it is greater, and it is good. So a depth-first traversal can carry that maximum downward, as a parameter. At each node:
- if
node.val >= maxSoFar, count the node; - compute the new maximum for the path, which includes this node;
- pass that new maximum to both children.
Both children receive the same value, because they share the path down to their parent and nothing from one branch is on the other branch's path. Each node is visited once.
For [3, 1, 4, 3, null, 1, 5], the visits are, in order, each node with the largest value above it:
3 (max above 3)
1 (max above 3)
3 (max above 3)
4 (max above 3)
1 (max above 4)
5 (max above 4)
The root gets its own value as the starting maximum, so it passes the test. The nodes whose value is at least the number shown are 3, 3, 4 and 5, which makes 4 in all.
Step by step
- Start the traversal in
goodNodesby calling the helpercountGoodonroot, withroot.valas the starting maximum. The root has nothing above it, so using its own value lets it pass. - Declare the helper
countGood(node, maxSoFar). It returns the number of good nodes in the tree undernode, wheremaxSoFaris the largest value on the path abovenode. - Base case. If
nodeisnull, return 0. An empty tree has no good nodes, and this check ends the recursion past the leaves. - Declare
countas 0. It will hold this node, if good, plus the good nodes below it. - Test this node. If
node.val >= maxSoFar, setcountto 1. One comparison checks the whole path, and equal values count as good. - Compute
newMaxas the larger ofmaxSoFarandnode.val. The children have this node on their path, so the bar they must reach may have risen. - Add the left subtree's count with a recursive call on
node.leftandnewMax. - Add the right subtree's count the same way.
- Return
count.
The solution in JavaScript
class Solution {
countGood(node, maxSoFar) {
if (!node) {
return 0;
}
let count = 0;
if (node.val >= maxSoFar) {
count = 1;
}
let newMax = Math.max(maxSoFar, node.val);
count += this.countGood(node.left, newMax);
count += this.countGood(node.right, newMax);
return count;
}
goodNodes(root) {
return this.countGood(root, root.val);
}
}
JavaScript details worth knowing:
this.countGood. Inside a class, one method calls another throughthis. WritingcountGood(...)alone would look for a variable of that name and fail with aReferenceError.!nodeas a null check. A missing child isnull, and!nullistrue. A real node is an object, which is always truthy, even when itsvalis 0.Math.maxwith two numbers returns the larger one, and works with negative values as well.- The method order doesn't matter.
goodNodesusescountGoodeven though it is defined after it, or before it in other layouts. A class body just declares methods. - Recursion depth. The tree is at most 800 levels deep. A chain of 800 nodes runs fine with this recursion. A far deeper chain, 100,000 nodes in a line, throws a
RangeErrorfrom the call stack, but the lesson's trees never get near that.
Complexity
Time: O(n). Every node is visited once, with a comparison and a Math.max.
Space: O(h) for the recursion, where h is the height of the tree: about log n for a balanced tree and up to n for a chain. Nothing else is stored.
Edge cases and common mistakes
- A single node.
[1]gives 1: the root is always good. - All negative values. Starting
maxSoFarat 0 breaks these trees. With that start,[-1, -2, -3]would count 0 good nodes, and[-5, -3, -9]would also count 0. The correct answers are 1 and 2. Starting fromroot.valavoids the problem. - Equal values.
[2, 2, 2]gives 3, since an equal value is not greater. Using>instead of>=would miss them: on[3, 3, null, 4, 2]it would count only the 4, instead of 3. - Increasing and decreasing paths.
[1, 2, 3, 4, 5]gives 5, since every node is at least the maximum above it.[5, 4, 3, 2, 1]gives 1: only the root is good. - Updating the maximum too late. The new maximum must include the current node before it goes to the children. Passing
maxSoFarunchanged would measure later nodes against an out-of-date bar. - Sharing one global maximum. A single variable updated across the whole traversal would let the left branch's values affect the right branch. The maximum belongs to a path, so it travels as a parameter.
Testing
[3, 1, 4, 3, null, 1, 5]gives4.[3, 3, null, 4, 2]gives3.[1]gives1.[-1, -2, -3]gives1.[-5, -3, -9]gives2.[5, 4, 3, 2, 1]gives1.[1, 2, 3, 4, 5]gives5.[2, 2, 2]gives3.- A chain of 800 nodes with increasing values (0 to 799), each the left child of the one above, gives
800.
