DSA problem
Count Good Nodes in Binary Tree
Given the root of a binary tree, a node X is called good if in the path from the root to X there are no nodes with a value greater than X.val. Return the number of good nodes in the binary tree.
Equivalently, walk from the root toward any node X; if X.val is at least as large as every value seen along the way, then X is good. The root is always good (no ancestors to violate the rule). A leaf may or may not be good depending on the chain of values above it.
The natural algorithm carries the running maximum so far down the tree as recursion descends. When we enter a node we compare its value with the maximum seen on the path; if node.val >= maxSoFar we add 1 to the running count and update the maximum for the children. Otherwise we leave the maximum unchanged. We then recurse into both children with this (possibly updated) maximum.
Although the information flow is top-down (we push the maximum downward), the aggregation of the result happens as the recursion unwinds — each call sums up the counts from its two children plus its own contribution. That makes this a textbook hybrid traversal: an order-agnostic DFS structurally, with a top-down running parameter and a post-order aggregation. The whole tree is visited once, giving O(n) time and O(h) stack space.
Examples
root = [3,1,4,3,null,1,5]4root = [3,3,null,4,2]3root = [1]1Constraints
- The number of nodes in the tree is in the range [1, 10^5].
- Each node's value is between [-10^4, 10^4].
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.