Problem overview
The method goodNodes receives the root of a binary tree, a TreeNode | null (the lesson provides the TreeNode class, with the fields val, left and right), and returns the number of good nodes. A node is good when no node on the path from the root down to it has a value greater than its own. A node that equals the largest value above it is still good, and the root is always good, because nothing is above it. The tree has at least one node.
For the tree [3,1,4,3,null,1,5] (level order, null for a missing child), the answer is 4. The root 3 is good. The 4 is good (path 3, 4), and so is the 5 (path 3, 4, 5). The 3 at the bottom left is good too: its path 3, 1, 3 has nothing 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 are good. The 2 is not, since its path 3, 3, 2 holds greater values.
Approach: carry the largest value down the path
One way to decide for each node is to walk back up to the root and compare. That takes up to O(n · h) time for a tree h levels deep. There is a much simpler way, based on one fact: a node is good exactly when its value is at least the largest value above it. One comparison covers the whole path.
So go down the tree with a depth-first search and carry that largest value with you, in a parameter named maxSoFar. At each node:
- If
node.val >= maxSoFar, the node is good and counts as 1. - The largest value on the path to the node's children is the larger of
maxSoFarandnode.val. Pass that to both children. - The answer for the node is its own count plus the answers for the left and right subtrees.
For the root, there is nothing above it, so the starting value is the root's own value: root.val >= root.val is true, and the root is counted. Starting from 0 would be wrong when all values are negative.
Here is the walk on the first example, printing each node's value and the maxSoFar it receives:
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 good
The left branch (1, then 3) is visited before the right branch (4, then 1 and 5). Four lines say "good", and the method returns 4. Both children of a node receive the same maxSoFar, because they share the path down to that node and nothing in the left branch is on the right branch's path.
Step by step
- Start the search from
goodNodes. Call a helper,countGood, onrootwithroot.valas the largest value so far, and return its answer. - Declare the helper above it, with the parameters
node(TreeNode | null) andmaxSoFar(number), returning anumber. - Base case: if
nodeisnull, return 0. An empty tree has no good nodes, and this stops the recursion past a leaf. - Declare a counter
countwithlet, starting at 0. It will hold this node (if it is good) plus the good nodes below. - Test the node: if
node.val >= maxSoFar, setcountto 1. Equal counts as good. - Compute
newMaxwithMath.max(maxSoFar, node.val): the largest value on the path down to this node, the node included. - Add the left subtree's count with
+=and a recursive call onnode.leftwithnewMax. - Do the same for the right subtree,
node.right. - Return
count.
The solution in TypeScript
class Solution {
countGood(node: TreeNode | null, maxSoFar: number): number {
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: TreeNode | null): number {
return this.countGood(root, root.val);
}
}
Details that matter in TypeScript:
- Calling the helper. Inside a class, a method calls another through
this:this.countGood(...). A barecountGood(...)would not find it. - Union type and the null check. The parameter type
TreeNode | nullis a compile-time note, erased when the code is compiled to JavaScript. The base caseif (!node)is what really protects the later linesnode.val,node.leftandnode.rightat run time. root.valingoodNodes. The statement promises at least one node, sorootis nevernullhere. The lessons compile with--strict false, which is why the compiler accepts readingroot.valon aTreeNode | null. If the root could benull, this line would throw aTypeErrorat run time.letversusconst.countchanges, so it needslet.newMaxnever changes after it is set, soconstwould also work.Math.maxreturns the larger of its arguments, here two numbers.
Complexity
Time: O(n). Each node is visited once, and each visit does a comparison, a Math.max and two recursive calls.
Space: O(h), where h is the depth of the tree. The only extra memory is the call stack, one frame per level. It is 800 frames at most for the lesson's trees, which Node handles easily; a chain of 800 nodes, each larger than the last, returns 800.
Edge cases and common mistakes
- A single node.
[1]gives 1: the root is always good. - All values negative.
[-1,-2,-3]gives 1. Only the root is good: -2 and -3 are each smaller than -1. StartingmaxSoFarat 0 instead ofroot.valwould make the root fail the test and return 0. - Equal values.
[-5,-5,-6,-4]gives 3: the root, the second -5 (equal, not smaller) and the -4. Using>instead of>=would reject the equal -5, and the root itself too. - A root with a smaller and a larger child.
[2,1,3]gives 2: the root and the 3. The 1 has a greater value above it. - Forgetting
newMax. PassingmaxSoFarunchanged to the children would compare every node only with the root and call a node good when a larger value sits between it and the root. - Sharing a global maximum. A single variable that is updated as you go lets the left branch's values affect the right branch. The maximum must belong to the path, which is why it travels as a parameter.
Testing
With a small function that builds a tree from a level-order array, the method returned:
[3,1,4,3,null,1,5]gives 4.[3,3,null,4,2]gives 3.[1]gives 1.[-1,-2,-3]gives 1.[-5,-5,-6,-4]gives 3.[2,1,3]gives 2.
