#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Definition for a binary tree node
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct NodeInfo {
    bool isPerfect;
    int height;
    int size;
};

int* perfectSizes;
int sizesCount;
int sizesCapacity;

void addPerfectSize(int size) {
    if (sizesCount >= sizesCapacity) {
        sizesCapacity *= 2;
        perfectSizes = (int*)realloc(perfectSizes, sizesCapacity * sizeof(int));
    }
    perfectSizes[sizesCount++] = size;
}

struct NodeInfo dfs(struct TreeNode* node) {
    struct NodeInfo result;
    
    if (!node) {
        result.isPerfect = true;
        result.height = 0;
        result.size = 0;
        return result;
    }
    
    // Single leaf node is perfect
    if (!node->left && !node->right) {
        addPerfectSize(1);
        result.isPerfect = true;
        result.height = 1;
        result.size = 1;
        return result;
    }
    
    // Node with only one child cannot be perfect
    if (!node->left || !node->right) {
        // Still need to explore the existing subtree
        if (node->left) dfs(node->left);
        if (node->right) dfs(node->right);
        result.isPerfect = false;
        result.height = 0;
        result.size = 0;
        return result;
    }
    
    // Recursively check both subtrees
    struct NodeInfo leftInfo = dfs(node->left);
    struct NodeInfo rightInfo = dfs(node->right);
    
    // Current subtree is perfect if both children are perfect and same height
    if (leftInfo.isPerfect && rightInfo.isPerfect && 
        leftInfo.height == rightInfo.height) {
        int currentSize = leftInfo.size + rightInfo.size + 1;
        addPerfectSize(currentSize);
        result.isPerfect = true;
        result.height = leftInfo.height + 1;
        result.size = currentSize;
        return result;
    }
    
    result.isPerfect = false;
    result.height = 0;
    result.size = 0;
    return result;
}

int compare(const void* a, const void* b) {
    return (*(int*)b - *(int*)a); // Descending order
}

int kthLargestPerfectSubtree(struct TreeNode* root, int k) {
    sizesCapacity = 1000;
    perfectSizes = (int*)malloc(sizesCapacity * sizeof(int));
    sizesCount = 0;
    
    dfs(root);
    qsort(perfectSizes, sizesCount, sizeof(int), compare);
    
    int result = (k <= sizesCount) ? perfectSizes[k - 1] : -1;
    free(perfectSizes);
    return result;
}