LeetCode 2792 - Count Nodes That Are Great Enough

The problem gives us the root of a binary tree and an integer k. We must determine how many nodes in the tree are considered "great enough". A node is great enough if two conditions are satisfied: 1. Its subtree contains at least k nodes. 2.

leetcodeharddivide-and-conquertreedepth-first-searchbinary-tree

LeetCode Problem 2792

Difficulty: 🔴 Hard
Topics: Divide and Conquer, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem gives us the root of a binary tree and an integer k. We must determine how many nodes in the tree are considered "great enough".

A node is great enough if two conditions are satisfied:

  1. Its subtree contains at least k nodes.
  2. Its value is greater than the values of at least k nodes in that same subtree.

Recall that a subtree rooted at a node includes the node itself and all of its descendants.

The important detail is that we are not comparing the node with nodes outside its subtree. Every comparison is local to that subtree.

For example, suppose a node has subtree values:

{1, 3, 5, 8}

and the node's value is 8 with k = 2.

Since there are three values smaller than 8, namely 1, 3, and 5, the node satisfies the second condition. Because the subtree size is also at least 2, the node is great enough.

The constraints are especially important:

  • The tree contains at most 10^4 nodes.
  • k <= 10

The small value of k is the key observation that enables an efficient solution. Even though the tree may contain many nodes, we never need to keep track of large sorted collections. We only care about whether there are at least k smaller values.

A few important edge cases stand out immediately:

  • A leaf node can never be great enough when k >= 1, because its subtree contains only itself and therefore has zero smaller values.
  • Duplicate values matter. The condition requires strictly smaller values, not smaller or equal.
  • Very unbalanced trees can create deep recursion paths.
  • If the subtree size is smaller than k, the node automatically fails regardless of its value.

Approaches

Brute Force Approach

The most direct solution is to process every node independently.

For each node:

  1. Traverse its entire subtree.
  2. Collect all values from that subtree.
  3. Count how many values are strictly smaller than the current node's value.
  4. Check whether that count is at least k.

This approach is straightforward and clearly correct because it explicitly computes the exact subtree contents for every node.

However, it is inefficient.

If the tree contains n nodes, then for every node we may traverse almost the entire tree again. In the worst case, such as a skewed tree, this becomes:

O(n^2)

With n = 10^4, this is too slow.

Key Insight

The crucial observation is that k is very small, at most 10.

We do not need the entire sorted list of subtree values. To determine whether a node is great enough, we only need to know the k smallest values in its subtree.

Why?

A node is great enough if there are at least k values smaller than it.

That means:

  • If the node is larger than the k-th smallest value in the subtree, then at least k smaller values exist.
  • Otherwise, fewer than k smaller values exist.

So instead of storing every subtree value, we can maintain only the smallest k values for each subtree.

This leads naturally to a postorder DFS:

  • Solve left subtree.
  • Solve right subtree.
  • Merge their smallest values.
  • Insert the current node value.
  • Keep only the smallest k values.

Because k is tiny, every merge operation is effectively constant time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Rebuilds subtree values for every node
Optimal O(n × k) O(h × k) Maintains only the k smallest subtree values

Here, h is the height of the tree.

Algorithm Walkthrough

Step 1: Use Postorder DFS

We process the tree bottom-up.

For each node, we first process:

  1. Left subtree
  2. Right subtree
  3. Current node

This order is important because the current node depends on information from its children.

Step 2: Return the k Smallest Values from Each Subtree

For every subtree, the DFS function returns a sorted list containing only the smallest k values in that subtree.

For example, if:

k = 3

and a subtree contains:

[8, 1, 6, 2, 9]

we only keep:

[1, 2, 6]

The larger values are irrelevant because they cannot affect whether ancestor nodes have at least k smaller values.

Step 3: Merge Child Results

At a node:

  • Retrieve the smallest lists from the left and right children.
  • Merge them together with the current node value.
  • Sort the combined values.
  • Truncate to size k.

Since each child contributes at most k elements, the total amount of work per node is small.

Step 4: Determine Whether the Node Is Great Enough

Suppose the merged sorted list is:

[1, 2, 5]

and k = 3.

The largest value in this list is the k-th smallest value of the subtree.

If the current node's value is strictly greater than this k-th smallest value, then there are at least k smaller values in the subtree.

So the condition becomes:

node.val > kth_smallest

Step 5: Count Valid Nodes

Whenever the condition holds, increment the answer.

Continue DFS until the entire tree has been processed.

Why it works

The algorithm works because every subtree returns exactly the information needed by its parent, namely the smallest k values in sorted order.

A node is great enough precisely when at least k subtree values are smaller than it. The k-th smallest subtree value completely determines this condition:

  • If the node value exceeds it, then at least k smaller values exist.
  • Otherwise, fewer than k smaller values exist.

Since every subtree summary is correct by induction, the final count is also correct.

Python Solution

from typing import List, Optional
import bisect

# 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 countGreatEnoughNodes(self, root: Optional[TreeNode], k: int) -> int:
        answer = 0

        def dfs(node: Optional[TreeNode]) -> List[int]:
            nonlocal answer

            if not node:
                return []

            left_values = dfs(node.left)
            right_values = dfs(node.right)

            merged = left_values + right_values

            bisect.insort(merged, node.val)

            merged.sort()

            if len(merged) > k:
                merged = merged[:k]

            if len(merged) == k and node.val > merged[-1]:
                answer += 1

            return merged

        dfs(root)

        return answer

The implementation follows the postorder traversal described earlier.

The dfs function returns the sorted list of the smallest k values in the current subtree.

For a null node, the subtree is empty, so we return an empty list.

For a non-null node:

  1. Recursively compute the left subtree summary.
  2. Recursively compute the right subtree summary.
  3. Combine both lists.
  4. Insert the current node value.
  5. Sort the combined list.
  6. Keep only the smallest k values.

The condition:

len(merged) == k and node.val > merged[-1]

checks whether the current node is larger than the k-th smallest value in the subtree.

Because each returned list has size at most k, the work done at each node remains very small.

Go Solution

package main

import "sort"

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func countGreatEnoughNodes(root *TreeNode, k int) int {
    answer := 0

    var dfs func(node *TreeNode) []int

    dfs = func(node *TreeNode) []int {
        if node == nil {
            return []int{}
        }

        leftValues := dfs(node.Left)
        rightValues := dfs(node.Right)

        merged := append(leftValues, rightValues...)
        merged = append(merged, node.Val)

        sort.Ints(merged)

        if len(merged) > k {
            merged = merged[:k]
        }

        if len(merged) == k && node.Val > merged[len(merged)-1] {
            answer++
        }

        return merged
    }

    dfs(root)

    return answer
}

The Go implementation mirrors the Python logic closely.

A few language-specific details are worth noting:

  • Go uses slices instead of Python lists.
  • sort.Ints sorts the slice in ascending order.
  • nil nodes return an empty slice.
  • Since values are at most 10^4, integer overflow is not a concern.

Worked Examples

Example 1

root = [7,6,5,4,3,2,1]
k = 2

The tree structure is:

        7
      /   \
     6     5
    / \   / \
   4  3  2  1

We process bottom-up.

Node Returned Smallest Values Great Enough?
4 [4] No
3 [3] No
6 [3,4] Yes, 6 > 4
2 [2] No
1 [1] No
5 [1,2] Yes, 5 > 2
7 [1,2] Yes, 7 > 2

Final answer:

3

Example 2

root = [1,2,3]
k = 1

Tree:

    1
   / \
  2   3

Processing:

Node Returned Smallest Values Great Enough?
2 [2] No
3 [3] No
1 [1] No

The root is not greater than any value in its subtree.

Final answer:

0

Example 3

root = [3,2,2]
k = 2

Tree:

    3
   / \
  2   2

Processing:

Node Returned Smallest Values Great Enough?
2 [2] No
2 [2] No
3 [2,2] Yes, 3 > 2

Final answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n × k log k) Each node processes at most 2k + 1 values
Space O(h × k) Recursive call stack plus stored lists

Since k <= 10, the sorting cost is effectively constant.

At every node, we merge at most:

k + k + 1

values.

Therefore, the algorithm behaves almost linearly with respect to the number of nodes.

The recursion depth depends on tree height:

  • Balanced tree: O(log n)
  • Skewed tree: O(n)

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1
root1 = TreeNode(
    7,
    TreeNode(6, TreeNode(4), TreeNode(3)),
    TreeNode(5, TreeNode(2), TreeNode(1))
)
assert solution.countGreatEnoughNodes(root1, 2) == 3  # balanced tree example

# Example 2
root2 = TreeNode(1, TreeNode(2), TreeNode(3))
assert solution.countGreatEnoughNodes(root2, 1) == 0  # no node has smaller subtree values

# Example 3
root3 = TreeNode(3, TreeNode(2), TreeNode(2))
assert solution.countGreatEnoughNodes(root3, 2) == 1  # duplicates handled correctly

# Single node tree
root4 = TreeNode(10)
assert solution.countGreatEnoughNodes(root4, 1) == 0  # subtree too small

# Skewed tree
root5 = TreeNode(5,
    TreeNode(4,
        TreeNode(3,
            TreeNode(2,
                TreeNode(1)
            )
        )
    )
)
assert solution.countGreatEnoughNodes(root5, 2) == 3  # deep recursion case

# All equal values
root6 = TreeNode(2, TreeNode(2), TreeNode(2))
assert solution.countGreatEnoughNodes(root6, 1) == 0  # strict inequality required

# Large k relative to subtree
root7 = TreeNode(5, TreeNode(1), TreeNode(2))
assert solution.countGreatEnoughNodes(root7, 5) == 0  # subtree sizes too small

# Mixed values
root8 = TreeNode(
    10,
    TreeNode(5, TreeNode(1), TreeNode(7)),
    TreeNode(20, TreeNode(15), TreeNode(25))
)
assert solution.countGreatEnoughNodes(root8, 3) == 2  # root and node 20

Test Summary

Test Why
Balanced example tree Verifies normal multi-level processing
Small tree with no valid nodes Ensures false positives are avoided
Duplicate values Confirms strict comparison handling
Single node tree Smallest possible input
Skewed tree Tests recursion depth behavior
All equal values Ensures equal values are not counted
Large k Verifies subtree size requirement
Mixed value tree Tests general correctness

Edge Cases

A very important edge case occurs when the subtree contains fewer than k nodes. In this situation, the node automatically fails the first condition. A buggy implementation might still attempt to compare values and incorrectly count the node. This implementation avoids that issue by only checking the condition when the maintained list size equals k.

Duplicate values are another subtle case. The problem requires strictly smaller values, not smaller or equal values. If the subtree contains many equal elements, a careless implementation could overcount. The condition:

node.val > merged[-1]

correctly enforces strict inequality.

Highly unbalanced trees are also important. A skewed tree behaves like a linked list and can produce recursion depth proportional to n. The algorithm still works correctly because each recursive call processes only a tiny fixed-size list. The time complexity remains efficient even in the worst tree shape.

Another tricky scenario occurs when the current node itself belongs among the smallest k values of the subtree. In that case, it cannot possibly have k smaller descendants. By truncating the merged list to the smallest k elements, the algorithm naturally captures this behavior without needing any special handling.