Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8

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.

graph TD;
G(7) --- F(6) & E(5)
F --- D(4) & C(3)
E --- B(2) & A(1)

Example 2:

1
2
3
4
5
6
7

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.

graph TD;
A(1) --- B(2) & C(3)

Example 3:

1
2
3
4
5
6
7

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.

graph TD;
C(3) --- B(2) & B1(2)

Constraints:

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

Solution

Method 1 – Postorder DFS with Subtree Size and Value Counting

Intuition

For each node, we need to know:

  • The size of its subtree (number of nodes).
  • How many nodes in its subtree have values less than the current node’s value.

We can use postorder DFS to compute the size and collect all values in the subtree, then use binary search (or counting) to efficiently count how many are less than the current node’s value.

Approach

  1. Traverse the tree in postorder (left, right, root).
  2. For each node, recursively get the sorted list of values in its left and right subtrees.
  3. Merge the two sorted lists and add the current node’s value.
  4. The size of the merged list is the subtree size.
  5. Use binary search to count how many values in the merged list are less than the current node’s value.
  6. If the subtree size is at least k and the count of values less than the node’s value is at least k, increment the answer.
  7. Return the answer after traversing the whole tree.

Code

 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
29
30

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int ans = 0, kk;
    std::vector<int> dfs(TreeNode* node) {
        if (!node) return {};
        auto l = dfs(node->left);
        auto r = dfs(node->right);
        std::vector<int> merged;
        merged.reserve(l.size() + r.size() + 1);
        std::merge(l.begin(), l.end(), r.begin(), r.end(), std::back_inserter(merged));
        auto it = std::lower_bound(merged.begin(), merged.end(), node->val);
        int less = it - merged.begin();
        merged.insert(it, node->val);
        int sz = merged.size();
        if (sz >= kk && less >= kk) ans++;
        return merged;
    }
    int countGreatEnoughNodes(TreeNode* root, int k) {
        ans = 0; kk = k;
        dfs(root);
        return ans;
    }
};
 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
29
30
31
32
33
34
35
36
37
38
39
40
41

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func CountGreatEnoughNodes(root *TreeNode, k int) int {
    var ans int
    var dfs func(*TreeNode) []int
    dfs = func(node *TreeNode) []int {
        if node == nil {
            return nil
        }
        l := dfs(node.Left)
        r := dfs(node.Right)
        merged := make([]int, 0, len(l)+len(r)+1)
        i, j := 0, 0
        for i < len(l) && j < len(r) {
            if l[i] < r[j] {
                merged = append(merged, l[i])
                i++
            } else {
                merged = append(merged, r[j])
                j++
            }
        }
        merged = append(merged, l[i:]...)
        merged = append(merged, r[j:]...)
        less := 0
        for less < len(merged) && merged[less] < node.Val {
            less++
        }
        merged = append(merged[:less], append([]int{node.Val}, merged[less:]...)...)
        if len(merged) >= k && less >= k {
            ans++
        }
        return merged
    }
    dfs(root)
    return ans
}
 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
29
30

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
class Solution {
    int ans = 0, kk;
    private List<Integer> dfs(TreeNode node) {
        if (node == null) return new ArrayList<>();
        List<Integer> l = dfs(node.left), r = dfs(node.right);
        List<Integer> merged = new ArrayList<>(l.size() + r.size() + 1);
        int i = 0, j = 0;
        while (i < l.size() && j < r.size()) {
            if (l.get(i) < r.get(j)) merged.add(l.get(i++));
            else merged.add(r.get(j++));
        }
        while (i < l.size()) merged.add(l.get(i++));
        while (j < r.size()) merged.add(r.get(j++));
        int less = 0;
        while (less < merged.size() && merged.get(less) < node.val) less++;
        merged.add(less, node.val);
        if (merged.size() >= kk && less >= kk) ans++;
        return merged;
    }
    public int countGreatEnoughNodes(TreeNode root, int k) {
        ans = 0; kk = k;
        dfs(root);
        return ans;
    }
}
 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

data class TreeNode(var `val`: Int, var left: TreeNode? = null, var right: TreeNode? = null)
class Solution {
    var ans = 0
    var kk = 0
    fun countGreatEnoughNodes(root: TreeNode?, k: Int): Int {
        ans = 0; kk = k
        fun dfs(node: TreeNode?): List<Int> {
            if (node == null) return emptyList()
            val l = dfs(node.left)
            val r = dfs(node.right)
            val merged = mutableListOf<Int>()
            var i = 0; var j = 0
            while (i < l.size && j < r.size) {
                if (l[i] < r[j]) merged.add(l[i++])
                else merged.add(r[j++])
            }
            while (i < l.size) merged.add(l[i++])
            while (j < r.size) merged.add(r[j++])
            val less = merged.indexOfFirst { it >= node.`val` }.let { if (it == -1) merged.size else it }
            merged.add(less, node.`val`)
            if (merged.size >= kk && less >= kk) ans++
            return merged
        }
        dfs(root)
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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: 'TreeNode', k: int) -> int:
        self.ans = 0
        def dfs(node):
            if not node:
                return []
            l = dfs(node.left)
            r = dfs(node.right)
            merged = sorted(l + r)
            less = 0
            while less < len(merged) and merged[less] < node.val:
                less += 1
            merged.insert(less, node.val)
            if len(merged) >= k and less >= k:
                self.ans += 1
            return merged
        dfs(root)
        return self.ans
 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
29
30
31
32
33
34
35
36

pub struct TreeNode {
    pub val: i32,
    pub left: Option<Box<TreeNode>>,
    pub right: Option<Box<TreeNode>>,
}

impl Solution {
    pub fn count_great_enough_nodes(root: Option<Box<TreeNode>>, k: i32) -> i32 {
        fn dfs(node: &Option<Box<TreeNode>>, k: i32, ans: &mut i32) -> Vec<i32> {
            if let Some(n) = node {
                let l = dfs(&n.left, k, ans);
                let r = dfs(&n.right, k, ans);
                let mut merged = Vec::with_capacity(l.len() + r.len() + 1);
                let (mut i, mut j) = (0, 0);
                while i < l.len() && j < r.len() {
                    if l[i] < r[j] {
                        merged.push(l[i]); i += 1;
                    } else {
                        merged.push(r[j]); j += 1;
                    }
                }
                merged.extend_from_slice(&l[i..]);
                merged.extend_from_slice(&r[j..]);
                let less = merged.iter().take_while(|&&x| x < n.val).count();
                merged.insert(less, n.val);
                if merged.len() as i32 >= k && less as i32 >= k { *ans += 1; }
                merged
            } else {
                vec![]
            }
        }
        let mut ans = 0;
        dfs(&root, k, &mut ans);
        ans
    }
}
 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

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0;
        this.left = left ?? null;
        this.right = right ?? null;
    }
}
class Solution {
    countGreatEnoughNodes(root: TreeNode | null, k: number): number {
        let ans = 0;
        function dfs(node: TreeNode | null): number[] {
            if (!node) return [];
            const l = dfs(node.left);
            const r = dfs(node.right);
            const merged = [...l, ...r].sort((a, b) => a - b);
            let less = 0;
            while (less < merged.length && merged[less] < node.val) less++;
            merged.splice(less, 0, node.val);
            if (merged.length >= k && less >= k) ans++;
            return merged;
        }
        dfs(root);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), since for each node we may merge and sort up to n values.
  • 🧺 Space complexity: O(n^2), for storing all subtree values at each node.