Problem overview
The method goodNodes receives the root of a binary tree with at least one node and returns how many of its 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, since nothing is above it. The lesson provides the TreeNode class, with an int val and the fields left and right.
For the tree [3, 1, 4, 3, null, 1, 5] (level order, null for a missing child) the answer is 4. The good nodes are the root 3, then 4, then 5 (path 3, 4, 5), and the 3 at the bottom left (path 3, 1, 3, where nothing is greater than 3). The 1 under the root is not good because 3 is greater, 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, because the path 3, 3, 2 contains greater values.
Approach: carry the largest value down the path
You could take each node and walk back up its path to look for a bigger value. That costs up to O(n · h) for a tree of height h. A depth-first walk avoids it by carrying what each node needs as it goes down: the largest value seen so far on the path above it.
A node is good exactly when its value is at least that largest value. One comparison checks the whole path. When the walk moves on to the children, the bar they must reach may have grown: it is the larger of the old bar and the current node's value. Both children get the same new bar, since they share the path down to their parent, and nothing in the left branch is on the right branch's path.
The recursion counts: each call returns the number of good nodes in the tree under its node, which is 0 for an empty tree, plus 1 if the node itself is good, plus the counts from its two subtrees. This is the walk for the two examples:
node 3 path 3 maxSoFar 3 good
node 1 path 3 -> 1 maxSoFar 3 not good
node 3 path 3 -> 1 -> 3 maxSoFar 3 good
node 4 path 3 -> 4 maxSoFar 3 good
node 1 path 3 -> 4 -> 1 maxSoFar 4 not good
node 5 path 3 -> 4 -> 5 maxSoFar 4 good
--
node 3 path 3 maxSoFar 3 good
node 3 path 3 -> 3 maxSoFar 3 good
node 4 path 3 -> 3 -> 4 maxSoFar 3 good
node 2 path 3 -> 3 -> 2 maxSoFar 3 not good
Every node is visited once, so the time is O(n).
Step by step
- Start the walk in
goodNodes. Call the helpercountGoodonrootwithroot.valas the largest value so far, and return its answer. The root has nothing above it, so starting from its own value lets it pass the test. Starting from 0 would be wrong: when every value is negative, the root would fail. - Write the helper's signature above
goodNodes: anintmethodcountGoodtaking aTreeNode nodeand anint maxSoFar. - Base case. If
node == null, return 0. An empty tree has no good nodes, and this stops the recursion past a leaf. - Declare
int count = 0. It will hold this node, if it is good, plus the good nodes below it. - If
node.val >= maxSoFar, setcount = 1. Equal counts as good: a node is only outdone by a strictly greater value. - Compute
newMaxasMath.max(maxSoFar, node.val). The children have this node on their path too. - Add the left subtree's count with
count += countGood(node.left, newMax). - Add the right subtree's count the same way, with
node.right. - Return
count.
The solution in Java
class Solution {
int countGood(TreeNode node, int maxSoFar) {
if (node == null) {
return 0;
}
int count = 0;
if (node.val >= maxSoFar) {
count = 1;
}
int newMax = Math.max(maxSoFar, node.val);
count += countGood(node.left, newMax);
count += countGood(node.right, newMax);
return count;
}
public int goodNodes(TreeNode root) {
return countGood(root, root.val);
}
}
Java details:
maxSoFaris a parameter, so each call has its own copy. Java passesintvalues by value. When the left call finishes, the right call still getsnewMaxunchanged, and neither call can disturb the other.+=on the result.count += countGood(...)adds the returned number to the local variable, which is the usual way to combine results from the two subtrees.- Using
valdirectly.node.valis anintfield, so the comparison andMath.maxwork on plain values with no boxing. - Recursion depth. The lesson allows trees up to 800 levels deep. A chain of 800 increasing values, where every node is good, runs fine and returns 800.
Complexity
Time: O(n). Each node is visited exactly once, and each visit does a comparison, a Math.max and two calls.
Space: O(h) for the call stack, where h is the height of the tree: O(n) for a chain and about O(log n) for a bushy tree. The method uses no other storage.
Edge cases and common mistakes
- A single node.
[1]gives 1, because the root is always good. - Negative values. Starting
maxSoFarat 0 fails when the values are negative. For the tree[-5, -7, -3, -9, -1]the method returns 3 (the nodes -5, -3 and -1), while a version that starts from 0 returns 0. - Equal values. A strict
>instead of>=rejects them. For the tree[2, 2, 2, 2]the method returns 4, and a strict comparison returns 0, since even the root fails it. - Not passing the new maximum. If the children get the old
maxSoFarinstead ofnewMax, a node under a bigger ancestor is judged against too small a bar. For[1, 5, null, 3]the method returns 2, because the 3 has a 5 above it, but a version that only ever compares against the root's 1 returns 3. - Comparing with the parent only. A node is good against its whole path, not just its parent. That is why the maximum is carried down.
Testing
[3, 1, 4, 3, null, 1, 5]gives 4.[3, 3, null, 4, 2]gives 3.[1]gives 1.[-5, -7, -3, -9, -1]gives 3.[2, 2, 2, 2]gives 4.[1, 5, null, 3]gives 2.[5, 4, null, 3, null, 2]gives 1: only the root is good.[1, 2, null, 3, null, 4]gives 4: every node is good.
