Approach Summary
DFS carrying the running max from root. A node is "good" if its value ≥ running max. Count such nodes.
How to Recognize This Pattern
- "Nodes not smaller than any ancestor"
- Pass max-so-far down the DFS; count nodes ≥ max
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(h)
Tags
Tree DFS BFS Binary Tree