All about Perfect Binary Trees + Approach using DFS
Perfect Binary Tree Explanation:\n\nA perfect binary tree is a binary tree where:\n1. All leaf nodes are at the same level.\n2. Every non-leaf node has exactly 
# **Perfect Binary Tree** Explanation:\n\nA **perfect binary tree** is a binary tree where:\n1. All leaf nodes are at the same level.\n2. Every non-leaf node has exactly two children (left and right).\n\n# **Properties of a Perfect Binary Tree:**\n- **Degree**: The degree of a node of a tree is defined as the number of children of that node. All the internal nodes have a degree of 2. The leaf nodes of a perfect binary tree have a degree of 0.\n  \n- **Number of leaf nodes**: If the height of the perfect binary tree is *h*, then the number of leaf nodes will be *2^h* because the last level is completely filled.\n\n- **Depth of a node**: Average depth of a node in a perfect binary tree is \u0398(ln(n)).\n\n- **Relation between leaf nodes and non-leaf nodes**: No. of leaf nodes = No. of non-leaf nodes + 1.\n\n- **Total number of nodes**: A tree of height *h* has total nodes = *2^(h+1) - 1*.\n\n- Each node of the tree is filled. So total number of nodes can be calculated as *2^0 + 2^1 + ... + 2^h = 2^(h+1) - 1*.\n\n- **Height of the tree**: The height of a perfect binary tree with *N* number of nodes = *log(N + 1) - 1 = \u0398(ln(n))*. This can be calculated using the relation shown while calculating the total number of nodes in a perfect binary tree.\n\n\n# What does it look like?\n\n![image.png](https://assets.leetcode.com/users/images/776654f0-e191-456d-a463-81a7262ba7aa_1733765912.2921693.png)\n\nA tree with only one root node is also known as a perfect binary tree.\n![image.png](https://assets.leetcode.com/users/images/78822b6b-dc1e-4cd6-bd68-8e2b48c76acf_1733765940.568217.png)\n\n\n\n# Approach\nHere we will basically just check that if the left sum and right sum of valid subtrees from our node is the same , if yes then we just add that to our `maxi` vector which stores the sizes of the valid perfect binary trees.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> maxi;\nint dfs(TreeNode* n) {\n    if (n == nullptr)\n        return 0;\n    if (int l = dfs(n->left), r = dfs(n->right); l == r) {\n        maxi.push_back(l + r + 1);\n        return l + r + 1;\n    }\n    return -1;\n}\nint kthLargestPerfectSubtree(TreeNode* root, int k) {\n    dfs(root);\n    if (maxi.size() < k)\n        return -1;\n    nth_element(begin(maxi), begin(maxi) + k - 1, end(maxi), greater{});\n    return maxi[k - 1];\n}\n};\n```
['C++']