Simple Recursion | DFS Traversal | C++ ✅
Intuition \nWhenever question related to binary tree comes , we first simply try to use DFS or BFS to get the expected answer. Since in this question we were re
#### Intuition \nWhenever question related to binary tree comes , we first simply try to use DFS or BFS to get the expected answer. Since in this question we were required to check if tree is perfect which means count of nodes on left and right are equal and leaves at same level. Hence we can use DFS and start building our answer once we reach leaf nodes.\n\n#### Logic\nOnce you reach a node check if it is a perfect binary tree with the help of left subtree and right subtree. For each node, if left and right are perfect, add the size of the perfect binart tree including root and return that. If it is not, return -1 which means it is not perfect.\n\nT.C. - O(N)\nS.C. - O(N)\n\n```\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    int dfs(TreeNode* root, vector<int>& ans) {\n\t\t// NULL root is a perfect binary tree of size 0\n        if(!root) return 0;\n        int lf = dfs(root->left); \n        int rt = dfs(root->right);\n        // checking if the left subtree and right subtree are perfect\n        if(lf == rt && lf !=-1 && rt!=-1) {\n\t\t\t// if yes, then the current root will also make one perfect tree \n            ans.push_back(lf+rt+1);\n            return lf+rt+1;\n        } else {\n\t\t\t// if not, then we simply return -1\n            return -1;\n        }\n    }\n    int kthLargestPerfectSubtree(TreeNode* root, int k) {\n\t\tvector<int> ans;\n        dfs(root, ans);\n        sort(ans.rbegin(), ans.rend());\n\t\t// if the we have more than k perfect binary trees, return the kth\n        if(ans.size()>=k) {\n            return ans[k-1];\n        }\n        return -1;\n    }\n};\n```
['Tree', 'Depth-First Search', 'C', 'Binary Tree']