A node is good if no node on the path from the root to it has a greater value. Return the number of good nodes.
Before you code
Whether a node is good depends on its ancestors, not its descendants, so the information must flow from the root down.
Hints
- Recurse with
(node, max_so_far), starting with the root's value. - The node is good if
node.val >= max_so_far. - Pass
max(max_so_far, node.val)to both children and add up the counts.
Production & complexity notes
When solving Count good nodes in binary tree on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Tree recursion patterns to reinforce the underlying pattern.
What it practices
Passing information down the tree, from Tree recursion patterns.