Skip to main content
Talentd

Count Nodes That Are Great Enough - Solution & Explanation

HardPremiumFree on FleetCodeDivide and ConquerTreeDepth-First SearchBinary Tree7 min read
Practice this problem

Problem Statement

You are given a root to a binary tree and an integer k. A node of this tree is called great enough if the followings hold:

  • Its subtree has at least k nodes.
  • Its value is greater than the value of at least k nodes in its subtree.

Return the number of nodes in this tree that are great enough.

The node u is in the subtree of the node v, if u == v or v is an ancestor of u.

 

Example 1:

Input: root = [7,6,5,4,3,2,1], k = 2
Output: 3
Explanation: Number the nodes from 1 to 7.
The values in the subtree of node 1: {1,2,3,4,5,6,7}. Since node.val == 7, there are 6 nodes having a smaller value than its value. So it's great enough.
The values in the subtree of node 2: {3,4,6}. Since node.val == 6, there are 2 nodes having a smaller value than its value. So it's great enough.
The values in the subtree of node 3: {1,2,5}. Since node.val == 5, there are 2 nodes having a smaller value than its value. So it's great enough.
It can be shown that other nodes are not great enough.
See the picture below for a better understanding.

Example 2:

Input: root = [1,2,3], k = 1
Output: 0
Explanation: Number the nodes from 1 to 3.
The values in the subtree of node 1: {1,2,3}. Since node.val == 1, there are no nodes having a smaller value than its value. So it's not great enough.
The values in the subtree of node 2: {2}. Since node.val == 2, there are no nodes having a smaller value than its value. So it's not great enough.
The values in the subtree of node 3: {3}. Since node.val == 3, there are no nodes having a smaller value than its value. So it's not great enough.
See the picture below for a better understanding.

Example 3:

Input: root = [3,2,2], k = 2
Output: 1
Explanation: Number the nodes from 1 to 3.
The values in the subtree of node 1: {2,2,3}. Since node.val == 3, there are 2 nodes having a smaller value than its value. So it's great enough.
The values in the subtree of node 2: {2}. Since node.val == 2, there are no nodes having a smaller value than its value. So it's not great enough.
The values in the subtree of node 3: {2}. Since node.val == 2, there are no nodes having a smaller value than its value. So it's not great enough.
See the picture below for a better understanding.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104]. 
  • 1 <= Node.val <= 104
  • 1 <= k <= 10

Approach Overview

Problem Overview: You are given a binary tree and an integer k. A node is considered great enough if there are at least k nodes in its subtree whose values are strictly smaller than the node’s value. The task is to count how many nodes satisfy this condition.

Approach 1: Brute Force Subtree Scan (O(n²) time, O(h) space)

For every node, traverse its entire subtree and collect all values. Count how many values are smaller than the current node’s value and check if that count is at least k. This can be implemented with a DFS from each node. The drawback is repeated work: the same subtree nodes are scanned many times. In a skewed tree, this leads to O(n²) time complexity with recursion stack space O(h). This approach is useful for understanding the problem but does not scale for large trees.

Approach 2: Postorder DFS with Size-K Heap (O(n * k log k) time, O(k * h) space)

The optimized solution processes the tree using a postorder Depth-First Search. Each recursive call returns the k smallest values found in that subtree. Instead of storing every value, keep a bounded max-heap (or sorted container) of size at most k. When combining results from the left and right children, merge their candidate values while maintaining the size limit.

At a node, you already have the k smallest values from its descendants. If the heap size is k and the current node’s value is greater than the largest value inside that heap (the k-th smallest), then there are at least k nodes in the subtree with smaller values. That node is counted as great enough. After the check, insert the current node’s value into the heap and trim it back to size k before returning it to the parent.

This technique works because the only values relevant to ancestors are the k smallest ones. Any larger values can never affect the comparison for nodes higher in the tree. The traversal naturally follows the recursive structure of a binary tree, while the merging of partial results resembles a divide and conquer strategy.

Recommended for interviews: The postorder DFS with a bounded heap is the expected solution. Mentioning the brute force approach first demonstrates you understand the definition of the subtree condition. The optimized method shows you can reduce redundant work by propagating only the necessary information (the k smallest values) during DFS.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subtree DFSO(n²)O(h)Useful for understanding the definition of the subtree condition or when constraints are very small
Postorder DFS with Size-K HeapO(n * k log k)O(k * h)General case for large trees; keeps only k smallest values per subtree

Video Solution

2792. Count Nodes That Are Great Enough (Leetcode Hard) • Programming Live with Larry • 191 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Count Nodes That Are Great Enough easy or hard?
Count Nodes That Are Great Enough is classified as Hard because it requires combining tree traversal with a top-k maintenance strategy. The challenge is reducing repeated subtree work while keeping the state small enough to pass efficiently up the recursion.
Count Nodes That Are Great Enough Python/Java solution
Implement a postorder DFS where each call returns a heap or sorted container holding at most k smallest subtree values. Merge child results, check if the current node’s value is greater than the k-th smallest value, update the answer, then insert the node value and trim the container.
How to solve Count Nodes That Are Great Enough in O(n)?
A near-linear solution uses a single DFS traversal where each node returns only the k smallest values from its subtree. By limiting the stored values to k and using a heap or small sorted structure, each node performs only small merges, keeping the overall runtime close to O(n * k log k).
What is the best approach for Count Nodes That Are Great Enough?
The most efficient approach uses postorder DFS combined with a bounded heap that stores the k smallest values in each subtree. During traversal, child results are merged and the node is checked against the k-th smallest value. This avoids scanning entire subtrees repeatedly and runs in O(n * k log k) time.
Is Count Nodes That Are Great Enough asked at Google/Amazon/Meta?
Problems combining DFS on trees with heap or top‑k tracking patterns are common in interviews at companies like Google, Amazon, and Meta. Variations often ask for maintaining top-k values or aggregating subtree information efficiently during traversal.
What data structure is used in Count Nodes That Are Great Enough?
The key data structures are a binary tree traversal using DFS and a bounded max-heap (or similar container) that keeps the k smallest values in each subtree. This structure enables quick comparison with the k-th smallest value.
What is the time complexity of Count Nodes That Are Great Enough?
The optimized DFS approach runs in O(n * k log k) time because each node merges candidate values while maintaining a heap of size at most k. Space complexity is O(k * h) due to recursion depth and the bounded containers passed up the tree.

Ready to solve this problem?

Practice Count Nodes That Are Great Enough with our built-in code editor and test cases.

Practice on FleetCode
Previous

Median of Two Sorted Arrays

Next

Merge k Sorted Lists