K th largest perfect subtree size in binary tree

Tree Depth-First Search Sorting Binary Tree

62.1% acceptance

Feb 27, 2026

152

You are given the root of a binary tree and an integer k. Return an integer denoting the size of the kth largest perfect binary subtree, or -1 if it doesn't exist. A perfect binary tree is a tree where all leaves are on the same level, and every parent has two children.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn kth_largest_perfect_subtree(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
    let mut sizes: Vec<i32> = Vec::new();
    
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, sizes: &mut Vec<i32>) -> i32 {
      match node {
        None => 0,
        Some(n) => {
          let n = n.borrow();
          let l = dfs(&n.left, sizes);
          let r = dfs(&n.right, sizes);
          if l == r && l >= 0 {
            let size = l + r + 1;
            sizes.push(size);
            size
          } else {
            -1
          }
        }
      }
    }
    
    dfs(&root, &mut sizes);
    sizes.sort_unstable_by(|a, b| b.cmp(a));
    let k = k as usize;
    if k <= sizes.len() {
      sizes[k - 1]
    } else {
      -1
    }
  }
}