Simple Post Order O(n.log(k)) Java  and C++ solution using min heap
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need to find the kth largest perfect subtree size in a binary search tree.\n\nA perf
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need to find the kth largest perfect subtree size in a binary search tree.\n\n**A perfect subtree is nothing but a binary tree where every node other than the leaf node has 2 children. in other words. Let\'s say we have a binary tree of height h. It is a perfect binary tree if it has exactly Pow(2, h) - 1 trees in the node.**\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSo for this problem, we need to calculate the height of every subtree and the number of nodes in the subtree.\n\n#### 1. Finding the height of the binary tree:\nHeight of a binary tree is nothing but $$max(height(left Subtree), height(rightSubtree)) + 1$$.\n\nSince we need to process the left subtree and right subtree before processing the root node, we use post order traversal.\n\n#### 2. Counting number of nodes in a tree\n\nSimilar to the height of the tree we can calculate no of nodes in a subtree by $$ nodes(leftSubtree) + nodes(rightSubtree) + 1$$. The +1 here is because we need to count the root node as well.\n\nPost order traversal can be used to calculate this as well. Instead of using two functions to compute these, we can simply return an array of size two for every node returning $$[height(tree), nodes(tree)]$$.\n\n#### 3. Checking if a tree is a perfect binary tree\n\nIf $$nodes(tree) == power(2,height(tree)) -1$$ then we can say that the subtree is a perfect binary tree.\n\n#### 4. Finding the kth largest perfect subtree size\nWe can find the kth largest perfect subtree size by storing the size of the subtree($$nodes(subtree)$$) in a heap.\n\nThere are two ways to do this in heaps\n-  **Max heap:** Use a max heap and pop the first k-1 elements to get the kth largest element.\n- **Min heap**: Min heap performs better than max heap in most of the cases. We push to a heap of size k. if the heap size is k we only push to the heap if the peak element is less than the current element. After pusing all the elements to the heap, the peek element is the kth largest element. \n\nThe time complextity for Min heap would be $$O(n.log(k))$$ as we maintain a heap of size k always. This will be in the worst case $$O(n.logn)$$ when $$k=n$$. However, max heap time complexity would be $$O(n.log(n))$$ in all cases, as we are pushing all the elements to the heap.\n\n# Complexity\n- Time complexity: $$O(n.log(k))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n.log(k))$$ for maintaining the min heap and  $$O(n)$$ for the post order traversal.\n- Space complexity: $$O(n)$$ for the min heap.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    int[] dfs(TreeNode root, PriorityQueue<Integer> heap, int k) {\n        if(root == null) return new int[]{0,0};\n\n        int[] left = dfs(root.left, heap, k);\n        int[] right = dfs(root.right, heap, k);\n\n        int[] result = {1 + Math.max(left[0], right[0]), left[1] + right[1] + 1};\n\n        if(result[1] == Math.pow(2, result[0]) -1) {\n            heap.offer(result[1]);\n            if(heap.size() > k) {\n                heap.poll();\n            } \n        }\n\n        return result;\n    }\n\n    public int kthLargestPerfectSubtree(TreeNode root, int k) {\n        PriorityQueue<Integer> heap = new PriorityQueue<>();\n\n        dfs(root, heap, k);\n\n        return heap.size() < k ? -1 : heap.poll();\n    }\n}\n```\n```C++ []\nclass Solution {\n    \npublic:\n    pair<int,int> dfs(TreeNode* root, priority_queue<int, vector<int>, greater<int>> &heap, int k) {\n        if(!root) return {0, 0};\n\n        auto left = dfs(root -> left, heap, k);\n        auto right = dfs(root -> right, heap, k);\n\n        pair<int, int> result = {1 + max(left.first, right.first), left.second + right.second + 1};\n\n        if(result.second == pow(2, result.first) -1) {\n            heap.push(result.second);\n            if(heap.size() > k) {\n                heap.pop();\n            } \n        }\n\n        return result;\n    }\n\n    int kthLargestPerfectSubtree(TreeNode* root, int k) {\n        priority_queue<int, vector<int>, greater<int>> heap; \n        \n        dfs(root, heap, k);\n        \n        return heap.size() < k ? -1 : heap.top();\n    }\n};\n```
['Heap (Priority Queue)', 'C++', 'Java']