A node is good if nothing on the path from the root is bigger. Walk down with DFS carrying the largest value seen so far, and count every node that meets or beats it, in O(n) time.
▼The problem
LeetCode 1448 (Medium). Given the root of a binary tree, a node X is *good* if no node on the path from the root to X has a value greater than X. Return the number of good nodes.
Examples (LeetCode's): [3,1,4,3,null,1,5] → 4 (the root 3, the 3 under the 1, the 4 and the 5), [3,3,null,4,2] → 3 and [1] → 1.
The solution
def goodNodes(root):
def dfs(node, best): # best: path max
if not node:
return 0
good = 1 if node.val >= best else 0
best = max(best, node.val)
return good + dfs(node.left, best) + dfs(node.right, best)
return dfs(root, root.val)Transcript
Count Good Nodes in Binary Tree. A node is good if no node on the path from the root down to it has a bigger value. Count the good nodes. Here, every node is a signal tower, as tall as its value.
Take this tree: three at the root, then one and four, then three, one and five. Three, three, four and five are good. Both ones sit below a three. The answer is four.
The naive way checks each node alone, walking its whole path again. That costs up to the tree's height per node, so n squared on a long chain.
The key idea: walk down once, and carry the biggest value on the path so far. A node is good if it's at least that big. Then pass the larger of the two to both children.
In code, a depth-first helper takes a node and the max so far. An empty spot counts zero. Add one if the node is good, plus both children's counts.
Let's walk it. The root, three, is good; the max is three. Going left, one is smaller, so not good. Its child, three, ties the max: good. On the right, four beats three: good, and the max becomes four. Below it, one is not good, but five is. Four good nodes.
Each node is visited once: order n time. The recursion goes as deep as the tree: order h space.
Carry the max, compare, pass it down. That's Count Good Nodes in Binary Tree.