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 X is good when no node on the path from the root down to X has a value greater than the value of X. A node that equals the largest value above it is still good, and the root is always good because nothing is above it. The lesson provides the TreeNode struct, with an int val and the pointers left and right.
In the first example, [3,1,4,3,NULL,1,5], the good nodes are the root 3, the 4, the 5 (path 3, 4, 5) and the 3 at the bottom left (path 3, 1, 3: nothing on it is greater than 3). The 1 under the root is not good because 3 is greater, and neither is the 1 under the 4. The answer is 4. In the second example, [3,3,NULL,4,2], the root, the 3 under it (an equal value is not greater) and the 4 are good, but the 2 is not, so the answer is 3. A tree with a single node has exactly one good node.
Approach: carry the maximum down the path
You could test every node by walking back up its path, but the paths overlap heavily and the total cost can reach O(n · h) for a tree h levels deep. There is a simpler way: walk down once and carry the information you need.
The only fact needed about the path above a node is the largest value on it. A node is good exactly when its value is at least that maximum, since one comparison covers the whole path. Going down, each node passes its children the larger of the incoming maximum and its own value, which is the maximum of the path that now includes it. Both children get the same number, because they share the path down to their parent, and nothing in the left branch is on the right branch's path.
The first example, walked from the top, with the maximum seen above each node:
node 3 maxSoFar=3 good
node 1 maxSoFar=3 not good
node 3 maxSoFar=3 good
node 4 maxSoFar=3 good
node 1 maxSoFar=4 not good
node 5 maxSoFar=4 goodFour lines say "good", so the answer is 4. The root starts with its own value as the maximum so far, which makes it good automatically.
Step by step
- Delegate from
goodNodes. Call a recursive helper,countGood, onrootwithroot->valas the largest value so far, and return its answer. Starting from the root's own value lets the root pass its own test. Starting from 0 would be wrong when every value is negative. - Write the helper's signature.
countGoodreturns anintand takes aTreeNode* nodeand anint maxSoFar, the largest value on the path abovenode. It goes abovegoodNodesin the class. - Handle the empty tree. If
nodeisnullptr(!node), return 0. An empty tree has no good nodes, and this check stops the recursion past a leaf. - Declare
countas anintstarting at 0. It will hold this node (if good) plus the good nodes below it. - Test this node. If
node->val >= maxSoFar, setcountto 1. Equal counts as good: only a strictly greater value outdoes a node. - Compute
newMax, the larger ofmaxSoFarandnode->val, withmax. The children have this node on their path too, so the value they must reach may now be this node's own. - Count the left subtree:
count += countGood(node->left, newMax). - Count the right subtree the same way with
node->right. - Return
count.
The solution in C++
class Solution {
public:
int countGood(TreeNode* node, int maxSoFar) {
if (!node) {
return 0;
}
int count = 0;
if (node->val >= maxSoFar) {
count = 1;
}
int newMax = max(maxSoFar, node->val);
count += countGood(node->left, newMax);
count += countGood(node->right, newMax);
return count;
}
int goodNodes(TreeNode* root) {
return countGood(root, root->val);
}
};
C++ details worth knowing:
- Null pointers.
!nodeis true for a null pointer. The base case has to come before any use ofnode->val, because dereferencing a null pointer is undefined behaviour. - Value parameter.
maxSoFaris passed by value, so each call has its own copy. The left call can't change the number that the right call sees. That is why both children get the samenewMaxwithout any bookkeeping. - Reading the root's value.
goodNodesusesroot->val, which is safe because the constraints promise at least one node. With a possibly empty tree you would need to testrootfirst. - Recursion depth. The tree is at most 800 levels deep, so the recursion fits easily on the call stack. A chain of 800 increasing values returns 800.
Complexity
Time: O(n). Every node is visited once and does a comparison, a max and two calls.
Space: O(h). The recursion keeps one frame per level of the tree, so the extra memory is proportional to the height h.
Edge cases and common mistakes
- All values negative. For
[-5, -7, -3, -9]the good nodes are the root -5 and the -3 (path -5, -3), so the answer is 2. Starting the maximum at 0 gives 0, because no negative value reaches it. Starting from the root's value, or from the smallest possibleint, gives 2. - Equal values. A tree where every value is 2, such as
[2, 2, 2, 2], has 4 good nodes. Using>instead of>=would count only the root. - A decreasing chain. For
[5, 4, NULL, 3, NULL, 2]only the root is good: every later node has a bigger value above it. - An increasing chain. For
[1, NULL, 2, NULL, 3, NULL, 4]every node is good, so the answer is 4. - Comparing with the parent only. A node bigger than its parent is not automatically good. In
[5, 1, NULL, 3]the 3 is bigger than its parent 1, but the root 5 is above it, so the answer is 1. - Passing the wrong maximum to a child. If the children receive
maxSoFarinstead ofnewMax, a node's own value is forgotten. For[1, 3, NULL, 2]the 2 has the 3 above it and is not good, so the answer is 2, but that mistake counts it and returns 3.
Testing
[3,1,4,3,NULL,1,5]gives 4.[3,3,NULL,4,2]gives 3.[1]gives 1.[-5,-7,-3,-9]gives 2.[2,2,2,2]gives 4.[5,4,NULL,3,NULL,2]gives 1.[1,NULL,2,NULL,3,NULL,4]gives 4.[5,1,NULL,3]gives 1.
