Problem overview
Given the root of a binary tree, goodNodes 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 TreeNode class, with a value and left and right children that may be null.
For the tree [3, 1, 4, 3, null, 1, 5] (level order, null for a missing child) 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 holds nothing greater than 3. The 1 under the root is not good because 3 is greater. For [3, 3, null, 4, 2] the answer is 3: the root, the 3 under it (equal is not greater) and the 4. The 2 fails.
Approach
You could test each node by walking back up its path. That needs a parent link and costs up to O(n · h) for a tree h levels deep. The better way carries the answer to the question down the path: the largest value seen so far on the path from the root. A node is good exactly when its value is at least that largest value, so one comparison checks the whole path. When we go down to a child, the largest value so far becomes the larger of the old one and the current node's value.
This is a depth-first search, written as a recursive helper, countGood, that returns the number of good nodes in the subtree under a node. Each node is visited once, so the time is O(n).
Step by step
- The entry point.
goodNodescallscountGood(root, root!!.value). The root has nothing above it, so starting from its own value lets it pass the test.rootis aTreeNode?, and!!says it isn'tnull, which holds because the tree has at least one node. Starting from 0 would be wrong: with all-negative values the root would fail. - The helper's signature.
countGoodtakes anodeof typeTreeNode?and anIntnamedmaxSoFar, the largest value on the path abovenode, and returns anInt. - The base case. If
node == null, return 0. An empty tree has no good nodes, and the check stops the recursion after a leaf. - The counter. Declare
var count = 0. It will hold this node (if it is good) plus the good nodes below it. It is avarbecause the next steps change it. - Is this node good? If
node.value >= maxSoFar, setcount = 1. Equal counts as good: only a strictly greater value above makes a node bad. - The new largest value. Store
maxOf(maxSoFar, node.value)inval newMax. The children have this node on their path too, so what they must reach may now be the node's own value. - Left subtree. Do
count += countGood(node.left, newMax). - Right subtree. Do the same with
node.right. Both children get the samenewMax: they share the path down to this node, and nothing in the left branch is on the right branch's path. - Return
count.
The solution in Kotlin
class Solution {
fun countGood(node: TreeNode?, maxSoFar: Int): Int {
if (node == null) {
return 0
}
var count = 0
if (node.value >= maxSoFar) {
count = 1
}
val newMax = maxOf(maxSoFar, node.value)
count += countGood(node.left, newMax)
count += countGood(node.right, newMax)
return count
}
fun goodNodes(root: TreeNode?): Int {
return countGood(root, root!!.value)
}
}
Kotlin details:
root!!throws aNullPointerExceptionifrootisnull. That is acceptable here because the statement promises at least one node. For a tree that may be empty, you would test fornullfirst.- After
if (node == null) return 0, Kotlin smart-castsnodeto a non-null type, sonode.valueandnode.leftare allowed. The children are nullable, which matches the parameter type ofcountGood. maxSoFaris a parameter, so each call has its own copy. The left branch can't change the value the right branch sees, which is why no undo step is needed on the way back up.count += countGood(...)is shorthand forcount = count + countGood(...)and works becausecountis avar.
A trace
For [3, 1, 4, 3, null, 1, 5], printing each node with the largest value above it (and the root's own value for itself), in the order the search visits them:
node 3: maxSoFar=3 good=true
node 1: maxSoFar=3 good=false
node 3: maxSoFar=3 good=true
node 4: maxSoFar=3 good=true
node 1: maxSoFar=4 good=false
node 5: maxSoFar=4 good=true
Four lines say good=true, so the method returns 4. The second 3 is good although it is not the biggest value in the tree: along its path 3, 1, 3 nothing exceeds it.
Complexity
Time: O(n). Every node is visited once and does constant work.
Space: O(h) for the recursion stack, where h is the height of the tree: O(log n) for a bushy tree and up to O(n) for a chain. The statement promises at most 800 levels, and a chain of 800 nodes (values 1 to 800, each the right child of the previous) runs fine and gives 800.
Edge cases and common mistakes
- Starting
maxSoFarat 0 or at a fixed small number. Values can be negative. For the tree[-3, -5, -1]the answer is 2 (the root -3 and the -1), but starting from 0 would count nothing and give 0. - Using
>instead of>=. Equal values are good. For[2, 2, 2, 2]every node is good and the answer is 4; with>only the root would be. - Passing the node's own value down without comparing. The children need the larger of the old maximum and this node's value, not just this node's value. In
[5, 4, 3, 2, 1]only the root is good (answer 1) because 5 stays the maximum all the way down. - Counting subtrees as one. Children of a bad node can still be good, so the search must continue below bad nodes.
- A single node gives 1: the root is always good.
Testing
Trees are written in level order. These were run against the solution above:
| Tree | Result |
|---|---|
[3, 1, 4, 3, null, 1, 5] | 4 |
[3, 3, null, 4, 2] | 3 |
[1] | 1 |
[-3, -5, -1] | 2 |
[5, 4, 3, 2, 1] | 1 |
[2, 2, 2, 2] | 4 |
