Problem overview
The method goodNodes receives the root of a binary tree and returns how many nodes are good. A node is good when no node on the path from the root down to it has a larger 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, whose nodes have val, left and right.
For the tree [3, 1, 4, 3, None, 1, 5] (level order, None for a missing child) the answer is 4. The good nodes are the root 3, the 4, the 5 below the 4, and the 3 at the bottom left, whose path 3, 1, 3 has nothing greater than 3. The two 1s are not good: a 3 sits above each of them. For [3, 3, None, 4, 2] the answer is 3: the root, the 3 below it (equal is not greater) and the 4. The 2 is not good, because the path 3, 3, 2 contains greater values. A single node, [1], gives 1.
The lesson asks for O(n) time, visiting each node once.
Approach: carry the largest value down the path
The direct idea walks back up from every node to check its path, which costs up to O(n · h) for a tree h levels deep. There is a cheaper way. Instead of looking back, carry what you need down the path as you go. The only thing a node needs to know about the path above it is the largest value on it. If node.val is at least that value, the node is good, and one comparison covers the whole path.
So the recursive helper countGood(node, maxSoFar) returns the number of good nodes in the tree under node, where maxSoFar is the largest value above it. At each node it:
- counts the node if
node.val >= maxSoFar; - computes the new largest value for the path, now including this node;
- adds the counts from the left and right subtrees, passing both the same new maximum, because they share the path down to this node and nothing in one branch is on the other's path.
The first call starts with the root's own value as maxSoFar, so the root passes its own test.
The calls on [3, 1, 4, 3, None, 1, 5], in the order the recursion visits the nodes (each node, then its left subtree, then its right):
| node | maxSoFar when reached | good? |
|---|---|---|
| 3 (root) | 3 | yes |
| 1 (left child) | 3 | no |
| 3 (under the 1) | 3 | yes |
| 4 (right child) | 3 | yes |
| 1 (left of 4) | 4 | no |
| 5 (right of 4) | 4 | yes |
Four rows say yes, so the answer is 4.
Step by step
- In
goodNodes, callself.countGood(root, root.val)and return its result. The root's own value is the starting maximum. - Write the helper's
defline: a methodcountGoodtakingself, anodeandmaxSoFar. - Base case: if
nodeisNone(not node), return 0. An empty tree has no good nodes, and this ends the recursion past a leaf. - Start a counter:
count = 0. It will hold this node (if good) plus the good nodes below it. - Test this node: if
node.val >= maxSoFar, setcount = 1. Equal counts as good. - Compute the new maximum for the path, node included:
newMax = max(maxSoFar, node.val). - Add the left subtree's count:
count += self.countGood(node.left, newMax). - Do the same for the right subtree. Both children get the same
newMax. - Return
count.
The solution in Python
class Solution:
def countGood(self, node, maxSoFar):
if not node:
return 0
count = 0
if node.val >= maxSoFar:
count = 1
newMax = max(maxSoFar, node.val)
count += self.countGood(node.left, newMax)
count += self.countGood(node.right, newMax)
return count
def goodNodes(self, root: Optional[TreeNode]) -> int:
return self.countGood(root, root.val)
Python details worth knowing:
- Passing the maximum as an argument. Each recursive call gets its own
maxSoFar. A value passed down never has to be undone when the recursion returns, which is the advantage over keeping a single shared variable that you must restore. not nodeis true forNone. ATreeNodeobject is truthy.- Call through
self. The helper is a method, so the recursive calls areself.countGood(...). +=on a local variable updatescountafter each recursive call returns. The built-inmaxpicks the larger of two values.- Recursion depth. Python's default limit is about 1000 nested calls. The constraints keep the tree at most 800 levels deep, and a chain of 800 nodes (each the left child of the one above, values 0 to 799) works and returns 800.
Complexity
Time: O(n). Each node is visited exactly once, and the work at a node is one comparison, one max and two calls.
Space: O(h), where h is the height of the tree, for the recursion stack: about log n in a well-balanced tree and up to n in a chain.
Edge cases and common mistakes
- Starting the maximum at 0. This fails when values are negative. The tree
[-1, -2, -3]has one good node, the root, but starting at 0 makes the root fail its own test and the count comes out as 0. For[-3, -1, -5]the answer is 2, and starting at 0 gives 0. Starting fromroot.valis right because the root has nothing above it. - Using
>instead of>=. Equal values are good. With>, even the root fails its own test, and[1]would give 0. For[3, 3, None, 4, 2]it gives 1 instead of 3. - Forgetting the node's own value in the path. The children must be compared with the larger of
maxSoFarandnode.val. PassingmaxSoFarunchanged ignores the values on the way down. - Decreasing lists. In
[5, 4, 3, 2, 1](the 4 and the 3 under the root, the 2 and the 1 under the 4) only the root is good, so the answer is 1. - Increasing lists. In
[1, 2, 3, 4, 5]every node is at least as big as everything above it, so all 5 are good. - All equal.
[2, 2, 2]gives 3. - A good node under a bad one. The 3 at the bottom left of the first example sits below a 1 that isn't good, and it is still good. A node's status depends on the largest value above it, not on whether its parent is good.
Testing
[3, 1, 4, 3, None, 1, 5]gives4.[3, 3, None, 4, 2]gives3.[1]gives1.[-1, -2, -3]gives1.[-3, -1, -5]gives2.[5, 4, 3, 2, 1]gives1.[1, 2, 3, 4, 5]gives5.[2, 2, 2]gives3.
