EASY DFS with MAP & BFS Solution
Complexity\n- Time complexity: for dfs- O(n log n) and u can make it O(n) by using unordered map  ||  for bfs TC is - O(n)\n Add your time complexity here, e.g.
# Complexity\n- Time complexity: for dfs- O(n log n) and u can make it O(n) by using unordered map  ||  for bfs TC is - O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n) for both \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# DFS\n```\nclass Solution {\npublic:\n    map<int,int>mp;\n    void helper(TreeNode* root,int level){\n        if(!root) return;\n        helper(root->left,level+1);\n        helper(root->right,level+1);\n        mp[level]+=root->val;\n    }\n    int maxLevelSum(TreeNode* root) {\n        helper(root,1);\n        int maxi=INT_MIN,maxlevel=0;\n        for(auto x:mp){\n            if(x.second>maxi){\n                maxi=x.second;\n                maxlevel=x.first;\n            }\n        }\n        return maxlevel;\n    }\n};\n```\n\n# BFS\n```\n  int maxLevelSum(TreeNode* root) {\n        queue<TreeNode*>q;\n        q.push(root);\n        int maxsum=INT_MIN,maxlevel=0,level=1;\n        while(!q.empty()){\n            int sum=0;\n            int n=q.size();\n            for(int i=0;i<n;i++){\n                TreeNode* node=q.front();\n                sum+=node->val;\n                q.pop();\n                if(node->left) q.push(node->left);\n                if(node->right) q.push(node->right);\n            }\n            if(sum>maxsum) {\n                maxsum=sum;\n                maxlevel=level;\n            }\n            level++;\n        }\n        return maxlevel;\n    }\n```
['Depth-First Search', 'C']