K-th Largest Perfect Subtree Size in Binary Tree
Source: leetcode
Difficulty: Medium
Tags: tree, depth-first-search, sorting, binary-tree

You are given the `root` of a **binary tree** and an integer `k`.


Return an integer denoting the size of the `kth` **largestperfect 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.


 


**Example 1:**



**Input:** root \= \[5,3,6,5,2,5,7,1,8,null,null,6,8], k \= 2


**Output:** 3


**Explanation:**


![](https://assets.leetcode.com/uploads/2024/10/14/tmpresl95rp-1.png)


The roots of the perfect binary subtrees are highlighted in black. Their sizes, in non\-increasing order are `[3, 3, 1, 1, 1, 1, 1, 1]`.\

The `2nd` largest size is 3\.



**Example 2:**



**Input:** root \= \[1,2,3,4,5,6,7], k \= 1


**Output:** 7


**Explanation:**


![](https://assets.leetcode.com/uploads/2024/10/14/tmp_s508x9e-1.png)


The sizes of the perfect binary subtrees in non\-increasing order are `[7, 3, 3, 1, 1, 1, 1]`. The size of the largest perfect binary subtree is 7\.



**Example 3:**



**Input:** root \= \[1,2,3,null,4], k \= 3


**Output:** \-1


**Explanation:**


![](https://assets.leetcode.com/uploads/2024/10/14/tmp74xnmpj4-1.png)


The sizes of the perfect binary subtrees in non\-increasing order are `[1, 1]`. There are fewer than 3 perfect binary subtrees.



 


**Constraints:**


- The number of nodes in the tree is in the range `[1, 2000]`.
- `1 <= Node.val <= 2000`
- `1 <= k <= 1024`




C++ solution:
class Solution {
public:
    vector<int>ans;
    pair<bool,int>make_tree(TreeNode* root){
        if(root==NULL){
            return {true,0};
        }

        pair<bool,int>l=make_tree(root->left);
        pair<bool,int>r=make_tree(root->right);

        if(l.first && r.first && l.second==r.second ){
            int s=l.second+r.second+1;
            ans.push_back(s);
            return {true,s};
        }

        return {false,0};
    }
    int kthLargestPerfectSubtree(TreeNode* root, int k) {

        if(root==NULL){
            return -1;
        }
        ans.clear();
        make_tree(root);

        sort(ans.begin(),ans.end(),greater<int>());

        if(ans.size()>=k){
            return ans[k-1];
        }
        return -1;
    }
};

Go solution:
// isPerfect checks if the subtree rooted at node is a perfect binary tree and returns its size
func isPerfect(node *TreeNode) (bool, int) {
 if node == nil {
  return true, 0
 }

 // Check left and right subtree
 leftPerfect, leftSize := isPerfect(node.Left)
 rightPerfect, rightSize := isPerfect(node.Right)

 if leftPerfect && rightPerfect && leftSize == rightSize {
  // The current node forms a perfect subtree
  return true, leftSize + rightSize + 1
 }

 // If it doesn't form a perfect subtree
 return false, 0
}

// kthLargestPerfectSubtreeSize returns the k-th largest perfect binary subtree size
func kthLargestPerfectSubtree(root *TreeNode, k int) int {
 var sizes []int

 var collectSizes func(node *TreeNode)
 collectSizes = func(node *TreeNode) {
  if node == nil {
   return
  }

  // Check if the current subtree is a perfect binary tree
  if perfect, size := isPerfect(node); perfect {
   sizes = append(sizes, size)
  }

  // Continue traversing left and right
  collectSizes(node.Left)
  collectSizes(node.Right)
 }

 // Collect sizes of all perfect binary subtrees
 collectSizes(root)

 // Sort sizes in descending order
 sort.Sort(sort.Reverse(sort.IntSlice(sizes)))

 // If k is valid, return the k-th largest size
 if k <= len(sizes) {
  return sizes[k-1] // k-1 for zero-based indexing
 }

 return -1 // Not enough perfect binary subtrees
}

Java solution:
class Solution {
    List<Integer> ans = new ArrayList<>();

    // Method to recursively check for perfect subtree and calculate its size
    public Pair<Boolean, Integer> makeTree(TreeNode root) {
        if (root == null) {
            return new Pair<>(true, 0);
        }

        Pair<Boolean, Integer> l = makeTree(root.left);
        Pair<Boolean, Integer> r = makeTree(root.right);

        if (l.getKey() && r.getKey() && l.getValue().equals(r.getValue())) {
            int s = l.getValue() + r.getValue() + 1;
            ans.add(s);
            return new Pair<>(true, s);
        }

        return new Pair<>(false, 0);
    }

    public int kthLargestPerfectSubtree(TreeNode root, int k) {
        if (root == null) {
            return -1;
        }

        ans.clear();
        makeTree(root);

        Collections.sort(ans, Collections.reverseOrder());

        if (ans.size() >= k) {
            return ans.get(k - 1);
        }

        return -1;
    }

}

JavaScript solution:
class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

class MinHeap {
    constructor() {
        this.heap = [];
    }

    insert(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    extractMin() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown(0);
        return min;
    }

    peek() {
        return this.heap[0];
    }

    getLength() {
        return this.heap.length;
    }

    bubbleUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] <= this.heap[index]) break;
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }

    bubbleDown(index) {
        while (true) {
            const leftChildIndex = 2 * index + 1;
            const rightChildIndex = 2 * index + 2;
            let smallest = index;

            if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] < this.heap[smallest]) {
                smallest = leftChildIndex;
            }

            if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[smallest]) {
                smallest = rightChildIndex;
            }

            if (smallest === index) break;
            [this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
            index = smallest;
        }
    }

    remove() {
        return this.extractMin();
    }
}

function kthLargestPerfectSubtree(root, k) {
    const minHeap = new MinHeap();

    function dfs(root, k, minHeap) {
        if (!root) return [true, 0];

        const [isLeftPerfect, leftCount] = dfs(root.left, k, minHeap);
        const [isRightPerfect, rightCount] = dfs(root.right, k, minHeap);

        const sum = leftCount + rightCount + 1;

        if (!isLeftPerfect || !isRightPerfect || leftCount !== rightCount) {
            return [false, sum];
        }

        if (minHeap.getLength() < k) {
            minHeap.insert(sum);
        } else if (sum > minHeap.peek()) {
            minHeap.remove();
            minHeap.insert(sum);
        }

        return [true, sum];
    }

    dfs(root, k, minHeap);

    return minHeap.getLength() < k ? -1 : minHeap.peek();
}

Python solution:
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def __init__(self):
        self.ans = []

    def make_tree(self, root):
        if root is None:
            return (True, 0)

        l = self.make_tree(root.left)
        r = self.make_tree(root.right)

        if l[0] and r[0] and l[1] == r[1]:
            s = l[1] + r[1] + 1
            self.ans.append(s)
            return (True, s)

        return (False, 0)

    def kthLargestPerfectSubtree(self, root, k):
        if root is None:
            return -1

        self.ans.clear()
        self.make_tree(root)

        self.ans.sort(reverse=True)

        if len(self.ans) >= k:
            return self.ans[k - 1]
        return -1

Ruby solution:
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @param {Integer} k
# @return {Integer}
def kth_largest_perfect_subtree(root, k)
  return -1 if root.nil?

  def helper(node)
    return [false, 0, []] if node.nil?

    if node.left.nil? && node.right.nil?
      return [true, 1, [1]]
    end

    left_perfect, left_height, left_sizes = helper(node.left)
    right_perfect, right_height, right_sizes = helper(node.right)

    current_sizes = left_sizes + right_sizes

    if node.left && node.right
      if left_perfect && right_perfect && left_height == right_height
        current_height = left_height + 1
        current_size = (2 ** current_height) - 1
        current_sizes << current_size
        return [true, current_height, current_sizes]
      else
        return [false, 0, current_sizes]
      end
    else
      return [false, 0, current_sizes]
    end
  end

  is_perfect, height, sizes = helper(root)
  sorted = sizes.sort.reverse
  sorted.size >= k ? sorted[k-1] : -1
end