100% runtime ✅ and memory ✅ beats Java solution | DFS | Min Heap
IntuitionWe need to find the k-th largest perfect subtree in a binary tree.
A perfect subtree is a subtree where all levels are completely filled.
The number of
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
We need to find the **k-th largest perfect subtree** in a binary tree.  
A **perfect subtree** is a subtree where all levels are completely filled.  
The number of nodes in a perfect subtree of height `h` is given by:  

{nodes} = (2^{h+1}) - 1

To solve this, we can use **DFS (Depth-First Search)** to determine the height of each subtree.

# Approach
<!-- Describe your approach to solving the problem. -->
1. **Perform DFS Traversal:**  
   - Compute the height of each subtree recursively.
   - If left and right subtree heights are different, it **cannot** be a perfect subtree.
   - If they are equal, the subtree is **perfect**, so we compute its height.
2. **Use a Min-Heap (`PriorityQueue`) to track top-k heights:**  
   - Maintain the **k-largest heights** encountered.
   - If the heap size exceeds `k`, remove the **smallest height**.
3. **Return the k-th largest height:**  
   - If fewer than `k` perfect subtrees exist, return `-1`.
   - Convert height `h` to number of nodes using \((1 << h) - 1\).

# Complexity
- **Time Complexity:**  
  - **O(n log k)** - DFS traverses each node (`O(n)`), and inserting/removing from the min-heap takes `O(log k)`.
  
- **Space Complexity:**  
  - **O(k + h)** - Min-heap stores `k` heights (`O(k)`), and DFS recursion takes `O(h)` space (where `h` is tree height).

# Code
```java []
class Solution {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // Min-heap to store top k heights
    int k; // Store k globally to access in DFS

    private int dfs(TreeNode root) {
        if (root == null)
            return 0;

        int left = dfs(root.left);
        int right = dfs(root.right);

        // If left and right heights are different, it's not a perfect subtree
        if (left == -1 || right == -1 || left != right)
            return -1;

        int height = left + 1; // Current subtree height

        // Maintain a min-heap of size k
        if (minHeap.size() < k) {
            minHeap.add(height);
        } else if (height > minHeap.peek()) {
            minHeap.poll(); // Remove the smallest element
            minHeap.add(height);
        }

        return height;
    }

    public int kthLargestPerfectSubtree(TreeNode root, int k) {
        this.k = k;
        dfs(root);

        if (minHeap.size() < k)
            return -1; // Not enough perfect subtrees

        int n = minHeap.peek(); // The k-th largest height
        return (1 << n) - 1; // Compute number of nodes in the perfect subtree
    }
}

['Tree', 'Depth-First Search', 'Sorting', 'Binary Tree', 'Java']