Problem overview
The function goodNodes receives root, a pointer to the top node of a binary tree with at least one node, and returns how many 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 X's value. A node whose value 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 type, with an integer Val and two pointers, Left and Right, that are nil when a child is missing.
In the first example, the root is 3. Its left child is 1, which has a left child 3. Its right child is 4, which has the children 1 and 5. 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: 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 4.
In the second example, the root 3 has a left child 3, which has the children 4 and 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 has greater values. A tree with only the root 1 has the answer 1.
The lesson asks for O(n) time, where n is the number of nodes, visiting each node once.
Approach: carry the largest value down the path
A direct way is to walk back up the path from every node and look for a greater value. That costs up to O(n * h) time for a tree h levels deep. The faster way carries what is needed down the path as the search goes.
A node is good exactly when its value is at least the largest value above it. So a recursive helper, countGood, receives a node and maxSoFar, the largest value on the path above it. One comparison, node.Val >= maxSoFar, tells whether the node is good, and the helper passes the updated maximum, the larger of maxSoFar and the node's own value, to both children. Both children share the path down to this node, and nothing in the left branch is on the right branch's path, so they get the same value.
The helper returns the number of good nodes in the tree under the node: 1 or 0 for the node itself, plus what the two subtrees report.
The first example, visited in order, with the maximum on the path above each node:
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
The root is called with its own value as maxSoFar. The bottom-left 3 equals the maximum above it (3), so it counts. The 1 under 4 sees a maximum of 4 and fails. Four lines say true, so the answer is 4.
Step by step
- Write
goodNodesas one line. It callscountGood(root, root.Val)and returns the 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 signature of
countGoodbelow it: a parameternodeof type*TreeNodeand anintnamedmaxSoFar, returningint. - Base case. If
node == nil, return 0. An empty tree has no good nodes, and the check stops the recursion past a leaf. - Start a counter
countat 0. It will hold this node, if it is good, plus the good nodes below it. - Test this node. If
node.Val >= maxSoFar, setcountto 1. Equal counts as good: a node is only outdone by a strictly greater value. - Update the maximum.
newMaxismax(maxSoFar, node.Val): the largest value on the path down to this node, the node included. The children have this node on their path. - Count the left subtree. Add
countGood(node.Left, newMax)tocountwith+=. - Count the right subtree the same way with
node.Right. - Return
count.
The solution in Go
func goodNodes(root *TreeNode) int {
return countGood(root, root.Val)
}
func countGood(node *TreeNode, maxSoFar int) int {
if node == nil {
return 0
}
count := 0
if node.Val >= maxSoFar {
count = 1
}
newMax := max(maxSoFar, node.Val)
count += countGood(node.Left, newMax)
count += countGood(node.Right, newMax)
return count
}
Go details worth knowing
- The path is a parameter, not a variable outside.
maxSoFaris passed by value, so each call has its own copy. The left branch can't change the value that the right branch sees, and there is nothing to undo when the recursion returns. - The built-in
max. Since Go 1.21maxis part of the language, so the lesson (Go 1.22) needs no helper. - A
nilroot panics.goodNodesreadsroot.Valstraight away. The lesson promises at least one node, so this is fine, butgoodNodes(nil)ends with "invalid memory address or nil pointer dereference".countGooditself handlesnilnodes. - Functions can come in any order.
goodNodesusescountGood, which is written below it.
Complexity
Time: O(n). Each node is visited once and does constant work.
Space: O(h), where h is the height of the tree, for the recursion: O(log n) for a balanced tree and O(n) for a chain. The tests go up to 800 levels, which recursion in Go handles easily.
Edge cases and common mistakes
- Negative values. Starting
maxSoFarat 0 is the classic mistake. For a root -5 with the children -7 and -2,goodNodesreturns 2 (the root and the -2), while a helper started at 0 would count 0. - Equal values. The comparison is
>=. With a strict>and the root's own value as the start, equal values stop counting and so does the root: a tree of four nodes that are all 5 gives 0 instead of 4. - Increasing and decreasing paths. A chain whose values grow as it goes down has every node good: 800 nodes give 800. A chain whose values shrink has only the root good: the answer is 1.
- Forgetting to update the maximum. If the children receive
maxSoFarinstead ofnewMax, a big value in the middle of the path is not remembered and nodes below it are wrongly counted as good. - Comparing with the parent only. The rule is about every node on the path, not just the parent. In a chain 5, 1, 3 the 3 is bigger than its parent 1, but the 5 above is greater, so only the root is good and the answer is 1. A version that compares each node with its parent returns 2.
- A shared counter. Keeping the count in a variable outside the function also works, but returning the count from each call keeps the helper free of state.
Testing
- Root 3, left 1 with child 3, right 4 with children 1 and 5, gives 4.
- Root 3, left 3 with children 4 and 2, gives 3.
- A single node 1 gives 1.
- Root -5 with the children -7 and -2 gives 2.
- A tree where every node is 5 (four nodes) gives 4.
- A chain of 800 nodes with increasing values gives 800, and with decreasing values gives 1.
