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.

Description Hints 3 Solution Video 11:13

2792. Count Nodes That Are Great Enough

Hard57.1% acceptancePremium elsewhere, free here

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, 10⁴].
1 <= Node.val <= 10⁴
1 <= k <= 10

Topics

Hints open one at a time

Hint 1

For each node, calculate a list of k values representing k smallest values in the subtree of that node.

Hint 2

To check if a node is great enough, get the described list in the first hint for its children and merge them. Since the resulting list may contain more than k elements, pick k smallest values and discard the extra ones.

Hint 3

Now check if the merged list has exactly k elements, and the current node's value is greater than the greatest element in the list, then that node is great enough.

11:13

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[7,6,5,4,3,2,1]
2

Input

[1,2,3]
1

Input

[3,1,2]
2

Your code is saved on this device.Solution