Count nodes that are great enough

Divide and Conquer Tree Depth-First Search Binary Tree

56.9% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::collections::BinaryHeap;
use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
  pub fn count_great_enough_nodes(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
    let mut count = 0;
    Self::dfs(&root, k as usize, &mut count);
    count
  }

  fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, k: usize, count: &mut i32) -> BinaryHeap<i32> {
    if let Some(n) = node {
      let n = n.borrow();
      let left = Self::dfs(&n.left, k, count);
      let right = Self::dfs(&n.right, k, count);
      let mut heap = BinaryHeap::new();
      for v in left.into_iter().chain(right.into_iter()) {
        heap.push(v);
        if heap.len() > k { heap.pop(); }
      }
      let less_count = heap.iter().filter(|&&v| v < n.val).count();
      if less_count >= k {
        *count += 1;
      }
      heap.push(n.val);
      if heap.len() > k { heap.pop(); }
      heap
    } else {
      BinaryHeap::new()
    }
  }
}