✅ Easy Solution || C++ || Beats 99.96% ✅
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem asks to find the k-th largest perfect subtree in a binary tree. A perfect s
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem asks to find the k-th largest perfect subtree in a binary tree. A perfect subtree is a subtree in which all leaf nodes are at the same level and every parent has exactly two children. To solve this, we traverse the tree, check whether each subtree is perfect, calculate the size of each perfect subtree, and store these sizes in a list. Finally, we retrieve the k-th largest value.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Helper Function:** A recursive function helper checks if a subtree rooted at root is a perfect subtree:\n- It recursively checks the left and right subtrees.\n- If both left and right subtrees are perfect and have the same size, the current subtree is also perfect. The size of the current perfect subtree is the sum of the sizes of the left and right subtrees plus 1 (for the current node).\n- The size of each perfect subtree is stored in a list ans.\n2. **Sorting and Returning the k-th Largest:** After collecting all the perfect subtree sizes in the list ans, sort it in descending order and return the k-th largest element.\n# Complexity\n- Time complexity:O(nlogn).\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n).\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n![Screenshot 2024-10-20 at 10.49.14\u202FAM.png](https://assets.leetcode.com/users/images/be1f5830-371d-4809-b340-515dfbc328f0_1729401757.563449.png)\n\n# Code\n```cpp []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    pair<bool,int>helper(TreeNode* root,vector<int> &ans){\n        if(root == NULL){\n            return {true,0};\n        }\n        //create left and right\n        pair<bool,int>leftPart = helper(root -> left,ans);\n        pair<bool,int>rightPart = helper(root -> right,ans);\n        //check prerfect subtree or not\n        if(leftPart.first && rightPart.first && leftPart.second == rightPart.second){\n            //sum\n            int sum = leftPart.second + rightPart.second + 1;\n            ans.push_back(sum);\n            return {true,sum};\n        }\n        return {false,0};\n    }\n    int kthLargestPerfectSubtree(TreeNode* root, int k) {\n        vector<int>ans;\n\n        if(root == NULL){\n            return -1;\n        }\n        //call helper function \n        helper(root,ans);\n        //sort decreasing order\n          sort(ans.begin(), ans.end(), greater<int>());\n        if (k > ans.size()) {\n            return -1;\n        }\n\n        return ans[k - 1]; // Return the k-th largest perfect subtree size\n    }\n};\n```
['Tree', 'Depth-First Search', 'Sorting', 'Binary Tree', 'C++']