Count Good Nodes in Binary Tree
Medium · Trees · Explanation and code example
Breadth First Search
How it works
A node is “good” if along the path from the root to that node, no earlier node has a value greater than it.
Using BFS, we can traverse level by level while carrying the maximum value seen so far for each path.
Whenever we visit a node, we compare its value with that max — if it's greater or equal, this node is good.
Each child inherits the updated maximum of its own path.
Steps
- Use a queue that stores pairs:
(node, maxSoFarOnPath). - Start by pushing
(root, -infinity)into the queue. - While the queue is not empty:
- Pop one
(node, maxVal). - If
node.val >= maxVal, increase the good-node count. - For each child:
- Push
(child, max(maxVal, node.val))into the queue.
- Push
- Pop one
- Return the total count.
Complexity
- Time complexity:
O(n) - Space complexity:
O(n)
Things to watch for
Using Strictly Greater Than Instead of Greater Than or Equal
A node is "good" if its value is greater than OR EQUAL to all ancestors. Using node.val > maxVal instead of node.val >= maxVal causes the root and equal-valued paths to be missed.
Initializing maxVal Too High
Starting with maxVal = 0 or maxVal = root.val can cause issues with negative values. Initialize with negative infinity or the root's value to correctly count the root as a good node.
Sharing maxVal Across Sibling Subtrees
The maximum value must be tracked per-path, not globally. Updating a shared variable instead of passing the new max to each recursive call causes incorrect comparisons across different branches.
Python code example
from collections import deque
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def goodNodes(self, root: TreeNode) -> int:
res = 0
q = deque()
q.append((root,-float('inf')))
while q:
node,maxval = q.popleft()
if node.val >= maxval:
res += 1
if node.left:
q.append((node.left,max(maxval,node.val)))
if node.right:
q.append((node.right,max(maxval,node.val)))
return res
C++ code example
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int goodNodes(TreeNode* root) {
int res = 0;
queue<pair<TreeNode*, int>> q;
q.push({root, -INT_MAX});
while (!q.empty()) {
auto [node, maxval] = q.front();
q.pop();
if (node->val >= maxval) {
res++;
}
if (node->left) {
q.push({node->left, max(maxval, node->val)});
}
if (node->right) {
q.push({node->right, max(maxval, node->val)});
}
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.