DFS O(n) solution beats 100%
Intuition\nFrom the persepective of a node:\nIt is a perfect subtree if left subtree ans right subtree are both perfect and the size of both subtree are equal.\
# Intuition\nFrom the persepective of a node:\nIt is a perfect subtree if `left subtree` ans `right subtree` are both perfect and the `size` of both subtree are equal.\nFurthermore, I have stored the size of these perfect ones in a list. This can be optimised to use less space.\n\n# Approach\n- Function `subtreeCalc` takes a node and check if it is a perfect subtree.\n- If yes, it stores size.\n\n# Complexity\n- Time complexity:\nO(n), where n is the total number of nodes in a tree. As this approach iterates over each node and its subtrees.\n\n# Code\n```C++ []\n#include <vector>\n#include <algorithm>\n\nclass Solution {\npublic:\n    std::pair<bool, int> subtreeCalc(TreeNode* node, std::vector<int>& sizes) {\n        if (node == nullptr) {\n            return {true, 0};\n        }\n\n        auto [isLeft, lsize] = subtreeCalc(node->left, sizes);\n        auto [isRight, rsize] = subtreeCalc(node->right, sizes);\n        \n        if (isLeft && isRight && lsize == rsize) {\n            sizes.push_back(lsize + 1 + rsize);\n            return {true, lsize + 1 + rsize};\n        }\n\n        return {false, 0};\n    }\n\n    int kthLargestPerfectSubtree(TreeNode* root, int k) {\n        std::vector<int> sizes;\n        subtreeCalc(root, sizes);\n        std::sort(sizes.rbegin(), sizes.rend());\n        return (k < sizes.size() + 1) ? sizes[k - 1] : -1;\n    }\n};\n```\n\n```python3 []\nclass Solution:\n    def subtreeCalc(self, node, sizes):\n        if node == None:\n            return (True, 0)\n\n        isLeft, lsize = self.subtreeCalc(node.left, sizes)\n        isRight, rsize = self.subtreeCalc(node.right, sizes)\n        \n        if isLeft and isRight and lsize == rsize:\n            sizes.append(lsize + 1 + rsize)\n            return (True, lsize + 1 + rsize)\n\n        return (False, 0)\n\n    def kthLargestPerfectSubtree(self, root: Optional[TreeNode], k: int) -> int:\n        sizes = []\n        self.subtreeCalc(root, sizes)\n        sizes.sort(reverse=True)\n        return sizes[k-1] if k < len(sizes) + 1 else -1\n        \n```\n
['Tree', 'Depth-First Search', 'Sorting', 'Binary Tree', 'Python3']