We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Nodes That Are Great Enough

Number: 3016

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Given the root of a binary tree and an integer k, we call a node “great enough” if:

  1. Its subtree (the node itself and all its descendants) has at least k nodes.
  2. Its value is greater than the value of at least k nodes in its subtree. Return the count of nodes that are “great enough.”

Key Insights

  • We must consider every node’s subtree and determine both the total count of nodes and the number of nodes whose values are strictly smaller than the node’s value.
  • The subtree of a node is defined recursively, so a depth-first search (DFS) approach fits naturally.
  • In order to quickly answer “how many nodes in the subtree have values less than node.val?”, we can keep the sorted order of values in the subtree.
  • Because k is small (up to 10), checking if the kth smallest value is less than the candidate node’s value is a useful shortcut.
  • Merging sorted lists from subtrees (using two‐pointer technique) allows computing the order statistics for each subtree.

Space and Time Complexity

Time Complexity: In the worst-case the merging process can be O(n^2) (e.g. in a degenerate tree) due to merging sorted lists at each node. Space Complexity: O(n) due to storing sorted lists representing subtree node values.

Solution

We perform a DFS over the tree. For each node, we recursively obtain the sorted list of values for its left and right subtrees. Then, we merge these two lists (as they are both sorted) into one sorted list representing all values from both subtrees. Before inserting the current node’s value into the merged list, we use binary search (or two‐pointer logic during merge) to determine how many existing values in the merged list are strictly less than the current node’s value. If the merged list’s size plus one (for the current node) is at least k and if the count of numbers strictly less than the node’s value is at least k, then the node is “great enough.” Finally, we insert the current node’s value into the merged list (maintaining sorted order) and return the resultant list upward. This process uses merging of sorted arrays and binary search insertion at each node.

Code Solutions

# 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

def countGreatEnoughNodes(root, k):
    # Global count of nodes satisfying the condition.
    count = 0

    # merge two sorted lists into one sorted list.
    def merge_lists(list1, list2):
        merged = []
        i, j = 0, 0
        while i < len(list1) and j < len(list2):
            if list1[i] <= list2[j]:
                merged.append(list1[i])
                i += 1
            else:
                merged.append(list2[j])
                j += 1
        if i < len(list1):
            merged.extend(list1[i:])
        if j < len(list2):
            merged.extend(list2[j:])
        return merged

    # Binary search to find the first index where value is >= target.
    def lower_bound(sorted_list, target):
        lo, hi = 0, len(sorted_list)
        while lo < hi:
            mid = (lo + hi) // 2
            if sorted_list[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        return lo

    def dfs(node):
        nonlocal count
        if not node:
            return []
        # recursively process left and right subtrees to get sorted lists.
        left_sorted = dfs(node.left)
        right_sorted = dfs(node.right)
        # merge the left and right sorted lists.
        merged_sorted = merge_lists(left_sorted, right_sorted)
        # Get the number of nodes in the merged list that are strictly less than node.val.
        num_smaller = lower_bound(merged_sorted, node.val)
        # Check if the subtree size (including current node) is at least k and 
        # node's value is greater than at least k nodes in its subtree.
        if len(merged_sorted) + 1 >= k and num_smaller >= k:
            count += 1
        # Insert current node's value into the sorted list.
        insert_index = lower_bound(merged_sorted, node.val)
        merged_sorted.insert(insert_index, node.val)
        return merged_sorted

    dfs(root)
    return count

# Example usage:
# Build the tree [7,6,5,4,3,2,1] and call countGreatEnoughNodes(root, 2)
← Back to All Questions