Problem overview
The method goodNodes receives the root of a binary tree, a TreeNode?, 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 integer val and the optional children left and right.
In the first example, the tree [3, 1, 4, 3, nil, 1, 5] has four good nodes: the root 3, the 4 (path 3, 4), the 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. The answer is 4. In the second, [3, 3, nil, 4, 2], the root, the 3 under it (an equal value is not greater) and the 4 are good, while the 2 is not, so the answer is 3. A tree with the single node [1] gives 1.
The statement asks for O(n) time, where n is the number of nodes.
Approach: carry the largest value down the path
You could check each node by walking back up its path, but trees give no parent links, and re-reading the path for every node costs up to O(n · h) for a tree h levels deep. It is simpler to carry what you need down as you go.
What you need is one number: the largest value seen on the path so far. A node is good exactly when its value is at least that number, because one comparison with the maximum covers the whole path. Then the node passes down the larger of the old maximum and its own value to its children.
That makes a recursive depth-first search. A helper, countGood, takes a node and the largest value above it, and returns the number of good nodes in the tree under that node. For the root, the largest value above it is the root's own value, so it always passes. Starting from 0 would be wrong: when every value is negative, the root would fail the test.
Here is a run of the first example. For each node, in the order the search reaches it, the table shows the largest value above it (the root uses its own) and whether it is good:
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, matching the answer 4. The 1 under the 4 sees a maximum of 4, because both the 3 and the 4 are on its path, and the search passed the larger one down.
Step by step
- Call the helper from
goodNodes. ReturncountGood(root, root!.val). The parameter is aTreeNode?, soroot!.valunwraps it with!, which is safe because the tree has at least one node. - Write the helper's signature.
countGoodtakes anodeof typeTreeNode?and anIntnamedmaxSoFar, both without argument labels, and returns anInt. - Handle the empty tree.
guard let node = node else { return 0 }unwraps the node, and an empty tree has no good nodes. This also stops the recursion when it steps past a leaf. - Declare a counter.
countis avarstarting at 0. It will hold this node, if it is good, plus the good nodes below it. - Test the node. If
node.val >= maxSoFar, setcountto 1. Equal counts as good: a node is only beaten by a strictly greater value. - Compute the maximum for the children.
newMaxismax(maxSoFar, node.val): the largest value on the path down to this node, the node included. - Add the left subtree.
count += countGood(node.left, newMax). - Add the right subtree the same way, with the same
newMax. The two children 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 Swift
class Solution {
func countGood(_ node: TreeNode?, _ maxSoFar: Int) -> Int {
guard let node = node else {
return 0
}
var count = 0
if node.val >= maxSoFar {
count = 1
}
let newMax = max(maxSoFar, node.val)
count += countGood(node.left, newMax)
count += countGood(node.right, newMax)
return count
}
func goodNodes(_ root: TreeNode?) -> Int {
return countGood(root, root!.val)
}
}
The Swift details worth knowing:
guard let node = node. It creates a new constant namednodethat holds the unwrapped value. If the optional isnil, theelseblock runs and has to leave the method. After theguard,nodeis a plainTreeNode, sonode.valneeds no!.root!. Force-unwrapping anilcrashes the program. Here it is safe because the constraints promise at least one node. For an optional that might be empty,guard letorif letis the safe way.varandlet.countchanges, so it is avar.newMaxis set once, so it is alet.- No labels. The
_in front of each parameter lets the call be written ascountGood(node.left, newMax). - Value parameters.
maxSoFaris anInt, which Swift copies into each call. The left call can't change the value that the right call receives, so the branches don't interfere. That is why the right child gets the samenewMaxafter the left subtree was counted.
Complexity
Time: O(n). Each node is visited once, and the work at a node is a comparison, a max and two calls.
Space: O(h), where h is the height of the tree, for the recursion stack. It is about log n for a balanced tree and n for a chain. The statement limits the depth to 800 levels.
Edge cases and common mistakes
- The root always counts. A single node gives 1.
- All values negative. Starting the maximum at 0 makes the root fail when its value is below 0. For the tree
[-5, -7, -3, nil, -9]the lesson's code returns 2 (the -5 and the -3), while the same code started from 0 returns 0. - Equal values. A node equal to the maximum above it is good. In the tree
[2, 2, 2, 2], all four nodes are good. - Comparing with the parent only. A node can be greater than its parent and still not good. In
[5, 1, nil, 3]the 3 is greater than its parent 1, but the 5 above is greater than 3, so only the root is good and the answer is 1. The comparison must be with the whole path, which the maximum carries. - Passing the wrong maximum to a child. The children need the maximum including the current node. Passing
maxSoFarinstead ofnewMaxwould ignore a node that raised the bar. - Ordered inputs.
[1, 2, 3, 4, 5], read in level order, gives 5: every value is at least as big as the ones above it.[9, 8, 7, 6, 5]gives 1, since only the root is good.
Testing
[3, 1, 4, 3, nil, 1, 5]gives 4.[3, 3, nil, 4, 2]gives 3.[1]gives 1.[-5, -7, -3, nil, -9]gives 2.[2, 2, 2, 2]gives 4.
