Count Good Nodes in Binary Tree

Problem

In a binary tree, call a node good if no node on the path from the root down to it (excluding itself) has a value strictly greater than the node's own value. In other words, a node is good when it is at least as large as every one of its ancestors. The root is always good. Given the root, return the number of good nodes in the tree.

• The tree has between 1 and 100,000 nodes; expect degenerate (chain-shaped) inputs.
• Node values are integers, possibly negative, with repeats allowed.

Examples

• root = [7, 2, 9, 8, None, 5, 12] → 4. The root 7 is good; 9 (path 7→9) and 12 (path 7→9→12) are good; 8 (path 7→2→8) is good because nothing above it exceeds 8. The 2 and the 5 each have a larger ancestor.
• root = [6, 6, None, 10, 4] → 3. Root 6, its child 6 (equal counts), and the 10 are good; the 4 has 6 above it.
• root = [5] → 1. A lone root is good.

Hints

1. To decide whether a node is good, what is the minimum information you need about its ancestors?
2. That information is a single number that only ever gets larger as you walk down. How does it update when you pass through a node?
3. Pre-order DFS carrying max_so_far; a node is good if node.val >= max_so_far, and you pass max(max_so_far, node.val) to its children.