Count Nodes That Are Great Enough

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

from sortedcontainers import SortedList

class Solution:
    def countGreatEnoughNodes(self, root: Optional[TreeNode], k: int) -> int:
        sorted_values = SortedList()
        self.great_nodes_count = 0

        def dfs(node):
            if not node: 
                return SortedList()
            left_subtree = dfs(node.left)
            right_subtree = dfs(node.right)

            if len(left_subtree) < len(right_subtree):
                left_subtree, right_subtree = right_subtree, left_subtree

            for value in right_subtree:
                left_subtree.add(value)

            index = left_subtree.bisect_left(node.val)
            left_subtree.add(node.val)

            if index >= k and len(left_subtree) >= k:
                self.great_nodes_count += 1
            return left_subtree

        dfs(root)
        return self.great_nodes_count