Count Good Nodes in Binary Tree
Medium · Trees · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
In a binary tree, a node X is called good if no node on the path from the root down to X has a value greater than X’s value.
Given the root of a binary tree, return the number of good nodes. The root is always good.
Examples
Input: root = [2,5,1,4,7,None,3] Output: 4
The good nodes are 2, 5, 7 and 3. The 4 is beaten by the 5 above it, and the 1 by the 2.
Input: root = [6,6,6] Output: 3
Equal values do not disqualify a node: all three are good.
Input: root = [5,2,8,6,None,7,9] Output: 4
Good: 5, the 6 below the 2, 8 and 9. The 2 is below the 5, and the 7 is below the 8.
Constraints
- 1 <= number of nodes <= 10^5
- -10^4 <= Node.val <= 10^4
Approaches
- Baseline: check every node against its whole path — time O(n·h), space O(h)
Follow-up
A breadth-first walk works just as well, as long as each queue entry carries its own path maximum. See the use cases for carrying two values down (the largest gap between a node and an ancestor) and for the same question on a tree given as a parent array.
Related problems
Start free on Cariara · Coding problems · System design studio
