Easy O(N) dfs traversal solution
\n# Approach\n# Base Case:\n\n1. If the root is NULL, it returns {true, 0}. This indicates that an empty subtree is considered perfect and its size is 0.\n# Rec
\n# Approach\n# Base Case:\n\n1. If the root is NULL, it returns {true, 0}. This indicates that an empty subtree is considered perfect and its size is 0.\n# Recursive Calls:\n\nThe function recursively checks the left and right subtrees by calling make_tree(root->left) and make_tree(root->right), storing the results in l and r.\n# Check for Perfect Subtree:\n\nIf both left (l.first) and right (r.first) subtrees are perfect (true) and their sizes (l.second and r.second) are equal, it confirms that the current subtree rooted at root is also perfect.\n# Calculate Subtree Size:\n\nThe size of this perfect subtree is calculated as l.second + r.second + 1 (1 for the root, and the sum of left and right subtree sizes).\n# Store the Result:\n\nThe size s is added to the ans vector to track all perfect subtree sizes.\n# Return:\n\nThe function returns {true, s}, indicating that this subtree is perfect and its size is s.\nIf the subtree is not perfect, it returns {false, 0}.\n\n# Complexity\n- Time complexity:\nO(Nlogn)\n\n- Space complexity:\nO(N)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int>ans;\n    pair<bool,int>make_tree(TreeNode* root){\n        if(root==NULL){\n            return {true,0};\n        }\n\n        pair<bool,int>l=make_tree(root->left);\n        pair<bool,int>r=make_tree(root->right);\n\n        if(l.first && r.first && l.second==r.second ){\n            int s=l.second+r.second+1;\n            ans.push_back(s);\n            return {true,s};\n        }\n\n        return {false,0};\n    }\n    int kthLargestPerfectSubtree(TreeNode* root, int k) {\n\n        if(root==NULL){\n            return -1;\n        }\n        ans.clear();\n        make_tree(root);\n\n        sort(ans.begin(),ans.end(),greater<int>());\n\n        if(ans.size()>=k){\n            return ans[k-1];\n        }\n        return -1;\n    }\n};\n```\n```java []\nimport java.util.*;\n\nclass Solution {\n    List<Integer> ans = new ArrayList<>();\n\n    // Method to recursively check for perfect subtree and calculate its size\n    public Pair<Boolean, Integer> makeTree(TreeNode root) {\n        if (root == null) {\n            return new Pair<>(true, 0);\n        }\n\n        Pair<Boolean, Integer> l = makeTree(root.left);\n        Pair<Boolean, Integer> r = makeTree(root.right);\n\n        if (l.getKey() && r.getKey() && l.getValue().equals(r.getValue())) {\n            int s = l.getValue() + r.getValue() + 1;\n            ans.add(s);\n            return new Pair<>(true, s);\n        }\n\n        return new Pair<>(false, 0);\n    }\n\n    public int kthLargestPerfectSubtree(TreeNode root, int k) {\n        if (root == null) {\n            return -1;\n        }\n\n        ans.clear();\n        makeTree(root);\n\n        Collections.sort(ans, Collections.reverseOrder());\n\n        if (ans.size() >= k) {\n            return ans.get(k - 1);\n        }\n\n        return -1;\n    }\n\n}\n\n```\n```python []\nclass TreeNode:\n    def __init__(self, val=0, left=None, right=None):\n        self.val = val\n        self.left = left\n        self.right = right\n\nclass Solution:\n    def __init__(self):\n        self.ans = []\n\n    def make_tree(self, root):\n        if root is None:\n            return (True, 0)\n\n        l = self.make_tree(root.left)\n        r = self.make_tree(root.right)\n\n        if l[0] and r[0] and l[1] == r[1]:\n            s = l[1] + r[1] + 1\n            self.ans.append(s)\n            return (True, s)\n\n        return (False, 0)\n\n    def kthLargestPerfectSubtree(self, root, k):\n        if root is None:\n            return -1\n\n        self.ans.clear()\n        self.make_tree(root)\n\n        self.ans.sort(reverse=True)\n\n        if len(self.ans) >= k:\n            return self.ans[k - 1]\n        return -1\n\n```\n```javascript []\nclass TreeNode {\n    constructor(val = 0, left = null, right = null) {\n        this.val = val;\n        this.left = left;\n        this.right = right;\n    }\n}\n\nclass Solution {\n    constructor() {\n        this.ans = [];\n    }\n\n    // Function to recursively check and calculate perfect subtree size\n    makeTree(root) {\n        if (root === null) {\n            return [true, 0];\n        }\n\n        let l = this.makeTree(root.left);\n        let r = this.makeTree(root.right);\n\n        if (l[0] && r[0] && l[1] === r[1]) {\n            let s = l[1] + r[1] + 1;\n            this.ans.push(s);\n            return [true, s];\n        }\n\n        return [false, 0];\n    }\n\n    kthLargestPerfectSubtree(root, k) {\n        if (root === null) {\n            return -1;\n        }\n\n        this.ans = [];\n        this.makeTree(root);\n\n        this.ans.sort((a, b) => b - a);\n\n        if (this.ans.length >= k) {\n            return this.ans[k - 1];\n        }\n        return -1;\n    }\n}\n\n```\n![c2d27b08-ffbe-4bc6-8b29-5fc4d8effd5f_1723775276.9029489.jpeg](https://assets.leetcode.com/users/images/67d4c577-4d03-4b9c-b295-b70a9c761a31_1728792685.7451727.jpeg)\n\n
['Array', 'Tree', 'Segment Tree', 'Binary Search Tree', 'Sorting', 'Binary Tree', 'C++', 'Java', 'Python3', 'JavaScript']