# K-th Largest Perfect Subtree Size in Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/k-th-largest-perfect-subtree-size-in-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/k-th-largest-perfect-subtree-size-in-binary-tree
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
---
## Problem
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.glich.co/dsa/k-th-largest-perfect-subtree-size-in-binary-tree/image0.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.glich.co/dsa/k-th-largest-perfect-subtree-size-in-binary-tree/image1.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.glich.co/dsa/k-th-largest-perfect-subtree-size-in-binary-tree/image2.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`

# Approaches
## Post-order Traversal with Sorting
This approach involves traversing the tree using a post-order Depth First Search (DFS) to identify all perfect binary subtrees and collect their sizes into a list. After the traversal is complete, the list of sizes is sorted in descending order to easily find the k-th largest element.
**Time:** O(N + M log M), where N is the number of nodes and M is the number of perfect subtrees. The traversal takes O(N) time. Sorting the M sizes takes O(M log M). In the worst case, M can be O(N), leading to a complexity of O(N log N). · **Space:** O(N), where N is the number of nodes in the tree. This is for the recursion stack in the worst case (a skewed tree) and for storing the sizes of the perfect subtrees, which can be up to O(N).
**Pros:** The logic is straightforward and directly follows the definition of a perfect binary tree.; It is relatively easy to implement and debug.
**Cons:** The time complexity is dominated by the sorting step, which is O(M log M), where M is the number of perfect subtrees. This is not optimal as we only need the k-th element, not a fully sorted list.; It requires storing all M sizes in memory, which could be inefficient if M is very large.
### Explanation
The core of this approach is a recursive helper function that performs a post-order traversal. We use post-order because to determine if a subtree at a given node is perfect, we must first have information about its left and right subtrees.

The helper function, let's call it `getHeight(node)`, returns the height of the subtree if it's perfect, or a sentinel value (like -2) if it's not. A `null` node is considered a perfect tree of height -1. For any non-null node, we recursively find the heights of its left and right subtrees. If both children form perfect subtrees of the same height, the current node's subtree is also perfect. Its height is `1 + height of a child`, and its size can be calculated using the formula `2^(height+1) - 1`. This size is then added to a global list.

Once the entire tree has been traversed, we have a list containing the sizes of all perfect subtrees. We then check if we have at least `k` such subtrees. If not, we return -1. Otherwise, we sort the list in descending order and pick the element at index `k-1`.

```java
import java.util.ArrayList; 
import java.util.Collections; 
import java.util.List;

class Solution {
    private List<Integer> perfectSubtreeSizes;

    public int kthLargestPerfectSubtreeSize(TreeNode root, int k) {
        perfectSubtreeSizes = new ArrayList<>();
        getHeight(root);

        if (perfectSubtreeSizes.size() < k) {
            return -1;
        }

        Collections.sort(perfectSubtreeSizes, Collections.reverseOrder());
        return perfectSubtreeSizes.get(k - 1);
    }

    // Returns the height of the subtree if it's perfect, otherwise -2.
    // Height of a null tree is -1.
    private int getHeight(TreeNode node) {
        if (node == null) {
            return -1;
        }

        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);

        // A subtree is perfect if both children form perfect subtrees of the same height.
        // -2 is a sentinel value for a non-perfect subtree.
        if (leftHeight != -2 && leftHeight == rightHeight) {
            int currentHeight = 1 + leftHeight;
            // Size of a perfect binary tree of height h is 2^(h+1) - 1
            int size = (1 << (currentHeight + 1)) - 1;
            perfectSubtreeSizes.add(size);
            return currentHeight;
        }

        // If it's not a perfect subtree, propagate the sentinel value.
        return -2;
    }
}
```
### Algorithm
- Initialize an empty list, `sizes`, to store the sizes of all perfect subtrees.
- Implement a recursive helper function, `getHeight(node)`, that performs a post-order traversal.
- The `getHeight` function should return the height of the subtree rooted at `node` if it's a perfect binary tree, and a special sentinel value (e.g., -2) if it's not. The height of a `null` node is defined as -1.
- Inside `getHeight(node)`:
  - Recursively call `getHeight` for the left and right children to get their respective heights.
  - If both children are perfect subtrees (i.e., their returned heights are not the sentinel value) and their heights are equal, then the subtree at `node` is also perfect.
  - If the current subtree is perfect, calculate its height (`1 + child_height`) and size (`2^(height+1) - 1`). Add this size to the `sizes` list.
  - Return the calculated height for the perfect subtree, or the sentinel value otherwise.
- After the initial call `getHeight(root)` completes, the `sizes` list will be populated.
- Check if `sizes.size()` is less than `k`. If it is, return -1.
- Sort the `sizes` list in descending order.
- Return the element at index `k-1` from the sorted list.

## Post-order Traversal with a Min-Heap
This optimized approach also uses a post-order DFS to identify perfect subtrees. However, instead of collecting all their sizes and sorting them, it uses a min-heap of size `k` to efficiently keep track of the k-th largest size. This avoids the cost of a full sort.
**Time:** O(N log k), where N is the number of nodes in the tree. The traversal of N nodes takes O(N) time. For each of the M perfect subtrees found, we perform a heap operation (insertion/deletion) which takes O(log k) time. Thus, the total time is O(N + M log k), which is bounded by O(N log k). · **Space:** O(N + k). The recursion stack can go up to O(N) in the worst case (for a skewed tree), and the min-heap requires O(k) space.
**Pros:** More efficient time complexity of O(N log k) compared to O(N log N) of the sorting approach.; Avoids storing all M sizes, which can be more memory-efficient if M is much larger than k.; Provides a better worst-case time complexity guarantee than other selection algorithms like Quickselect.
**Cons:** The logic is slightly more complex than the sorting approach due to the use of a heap.; The space complexity includes the heap, which adds an O(k) factor.
### Explanation
The traversal logic for identifying perfect subtrees remains identical to the first approach. We use the same `getHeight(node)` recursive function that returns a subtree's height if it's perfect and a sentinel value if it's not.

The key improvement lies in how we process the sizes of the perfect subtrees we discover. We use a min-heap (implemented as a `PriorityQueue` in Java) with a maximum size of `k`.

Whenever the `getHeight` function identifies a perfect subtree and calculates its `size`, it performs the following steps:
1.  Adds the `size` to the min-heap.
2.  Checks if the heap's size has exceeded `k`. If it has, it removes the smallest element from the heap (the element at the top). 

This process ensures that the min-heap always contains the `k` largest sizes found so far. After the entire tree has been traversed, the root of the heap will hold the k-th largest size.

Finally, we check if the heap contains `k` elements. If it has fewer, we return -1. Otherwise, we return the value at the top of the heap (`minHeap.peek()`).

```java
import java.util.PriorityQueue;

class Solution {
    private PriorityQueue<Integer> minHeap;
    private int k;

    public int kthLargestPerfectSubtreeSize(TreeNode root, int k) {
        this.minHeap = new PriorityQueue<>();
        this.k = k;
        getHeight(root);

        if (minHeap.size() < k) {
            return -1;
        }
        return minHeap.peek();
    }

    // Returns the height of the subtree if it's perfect, otherwise -2.
    private int getHeight(TreeNode node) {
        if (node == null) {
            return -1; // Height of an empty tree
        }

        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);

        if (leftHeight != -2 && leftHeight == rightHeight) {
            int currentHeight = 1 + leftHeight;
            int size = (1 << (currentHeight + 1)) - 1;
            
            minHeap.offer(size);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
            
            return currentHeight;
        }

        return -2; // Sentinel for non-perfect subtree
    }
}
```
### Algorithm
- Initialize a min-heap (PriorityQueue in Java) to store the `k` largest sizes found so far.
- Implement the same recursive helper function, `getHeight(node)`, as in the sorting approach.
- Inside `getHeight(node)`, when a perfect subtree is found with a calculated `size`:
  - Add the `size` to the min-heap.
  - If the size of the heap becomes greater than `k`, remove the smallest element by calling `poll()`. This maintains the heap's size at `k` and ensures it holds the `k` largest elements seen.
- After the initial call `getHeight(root)` completes, the traversal is done.
- Check if the final size of the min-heap is less than `k`. If it is, it means there are fewer than `k` perfect subtrees, so return -1.
- Otherwise, the k-th largest element is the smallest value in the heap, which is at the root. Return this value using `peek()`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private List < Integer > nums = new ArrayList <>(); public int kthLargestPerfectSubtree ( TreeNode root , int k ) { dfs ( root ); if ( nums . size () < k ) { return - 1 ; } nums . sort ( Comparator . reverseOrder ()); return nums . get ( k - 1 ); } private int dfs ( TreeNode root ) { if ( root == null ) { return 0 ; } int l = dfs ( root . left ); int r = dfs ( root . right ); if ( l < 0 || l != r ) { return - 1 ; } int cnt = l + r + 1 ; nums . add ( cnt ); return cnt ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int kthLargestPerfectSubtree ( TreeNode * root , int k ) { vector < int > nums ; auto dfs = [ & ]( auto && dfs , TreeNode * root ) -> int { if ( ! root ) { return 0 ; } int l = dfs ( dfs , root -> left ); int r = dfs ( dfs , root -> right ); if ( l < 0 || l != r ) { return - 1 ; } int cnt = l + r + 1 ; nums . push_back ( cnt ); return cnt ; }; dfs ( dfs , root ); if ( nums . size () < k ) { return - 1 ; } ranges :: sort ( nums , greater < int > ()); return nums [ k - 1 ]; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def kthLargestPerfectSubtree ( self , root : Optional [ TreeNode ], k : int ) -> int : def dfs ( root : Optional [ TreeNode ]) -> int : if root is None : return 0 l , r = dfs ( root . left ), dfs ( root . right ) if l < 0 or l != r : return - 1 cnt = l + r + 1 nums . append ( cnt ) return cnt nums = [] dfs ( root ) if len ( nums ) < k : return - 1 nums . sort ( reverse = True ) return nums [ k - 1 ]
```