Basic Traversal
Intuition\nFor complete Binary Tree these are total nodes in that complete Binary tree\n1,3,7,15,31\n\n# Hint \n 1 & (1+1) = 0\n 3 & (3+1) = 0\n 7 & (7+1) = 0\n
# Intuition\nFor complete Binary Tree these are total nodes in that complete Binary tree\n1,3,7,15,31\n\n# Hint \n 1 & (1+1) = 0\n 3 & (3+1) = 0\n 7 & (7+1) = 0\n x & (x+1) = 0\n Consider this as hint\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDo simple Traversal, handle all 3 general cases:\n1. If node is NULL\n```\nif(root == NULL){\n    return 0;\n}\n``` \n2. If node doesn\'t have child nodes then push 1 to result vector\n```\nif(root->left == NULL && root->right == NULL){\n    ans.push_back(1);\n    return 1;\n}\n``` \n3. If node does have child nodes, then push left subtree and right subtree count to result vector based on the above Hint condition. Consider at least the count of child nodes greater than 0. This makes sure it\'s not a leaf node and satisfies the Hint condition.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n*logn)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(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),\n * right(right) {}\n * };\n */\nclass Solution {\npublic:\n    vector<int> ans;\n    int dfs(TreeNode* src) {\n        \n        if (!src)\n            return 0;\n        if ( src->left==NULL && src->right==NULL ) {\n            ans.push_back(1);\n            return 1;\n        }\n\n        int lt = dfs(src->left);\n        int rt = dfs(src->right);\n\n        int tot = lt + rt + 1;\n\n        if ( !(tot & (tot + 1)) && lt+rt>0 ) {\n            ans.push_back(tot);\n            return tot;\n        }\n        return 0;\n    }\n    int kthLargestPerfectSubtree(TreeNode* root, int k) {\n        dfs(root);\n        sort(ans.begin(), ans.end(), greater<int>());\n        if (ans.size() < k)\n            return -1;\n        return ans[k - 1];\n    }\n};\n```
['Tree', 'C++']