Count Good Nodes in Binary Tree — Problem & Solution
Count Good Nodes in Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Good Nodes in Binary Tree is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Google, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, call a node good if no node on the path from the root down to it has a value larger than its own.
Return the number of good nodes in the tree.
Example 1
Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: The good nodes are the root 3, 4, 5 (above 3 and 4) and the left 3 (nothing above it is larger than 3).
Example 2
Input: root = [3,3,null,4,2]
Output: 3
Explanation: 3, its child 3 and 4 are good; 2 has the larger 3 above it.
Example 3
Input: root = [1]
Output: 1
Explanation: The root is always good.
Constraints
1 <= number of nodes <= 10^5-10^4 <= Node.val <= 10^4
Hints for Count Good Nodes in Binary Tree
Hint 1
A node is good exactly when its value is at least the maximum of all values above it.
Hint 2
So walk down the tree carrying the largest value seen on the current path.
Hint 3
Count the node if its value is at least that maximum, then pass
max(maximum, node.val)to its children.
How to solve Count Good Nodes in Binary Tree
Carry the maximum value of the path from the root during a depth-first walk; a node is good when it is not smaller than that maximum.
Approach
- Call
walk(root, root.val). - At a node: it is good if
node.val >= maxSoFar; setmaxSoFar = max(maxSoFar, node.val). - Return 1 (if good) plus the counts from both children with the updated maximum.
Why it works
The path from the root to a node is the path to its parent plus the node itself, so the maximum above a child is the parent's maximum updated with the parent's value — exactly what is passed down. Comparing against it checks the definition directly.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion
Pitfalls
- Equal values do not break goodness: compare with
>=. - Starting the maximum at 0 is wrong when values are negative — start with the root's value.
Reference solution
Python
from typing import Optional
def goodNodes(root: Optional[TreeNode]) -> int:
def walk(node, top):
if node is None:
return 0
good = 1 if node.val >= top else 0
top = max(top, node.val)
return good + walk(node.left, top) + walk(node.right, top)
return walk(root, root.val)Java
public static int goodNodes(TreeNode root) {
return goodWalk(root, root.val);
}
static int goodWalk(TreeNode node, int top) {
if (node == null) return 0;
int good = node.val >= top ? 1 : 0;
top = Math.max(top, node.val);
return good + goodWalk(node.left, top) + goodWalk(node.right, top);
}C++
int goodWalk(TreeNode* node, int top);
int goodNodes(TreeNode* root) {
return goodWalk(root, root->val);
}
int goodWalk(TreeNode* node, int top) {
if (!node) return 0;
int good = node->val >= top ? 1 : 0;
top = max(top, node->val);
return good + goodWalk(node->left, top) + goodWalk(node->right, top);
}JavaScript
var goodNodes = function(root) {
return goodWalk(root, root.val);
};
var goodWalk = function(node, top) {
if (node === null) return 0;
var good = node.val >= top ? 1 : 0;
top = Math.max(top, node.val);
return good + goodWalk(node.left, top) + goodWalk(node.right, top);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)