Count Good Nodes in Binary Tree
The key idea
A node is good when no ancestor on its root-to-node path has a larger value, i.e. the node's value is at least the maximum value seen on the way down. Carry that running maximum into each recursive call: a node is good exactly when its value is >= the max-so-far, and you then pass max(max-so-far, node.value) to its children.
Problem
You are given the root of a binary tree. A node X in the tree is called good if, on the path from the root down to X, there is no node with a value strictly greater than X. The root itself is always good. Return the total number of good nodes in the binary tree.
Constraints
- The number of nodes in the binary tree is in the range [1, 10^5].
- Each node's value is between [-10^4, 10^4].
Examples
Input: root = [3,1,4,3,null,1,5]
Output: 4
Input: root = [3,3,null,4,2]
Output: 3
Input: root = [1]
Output: 1
Complexity
Time: O(n) Space: O(h)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY