C++/DFS
\n\n// The simple logic behind this problem is that u need to check the height of the left and right subtree for every node. \n// case-1: If both left and right
\n\n// The simple logic behind this problem is that u need to check the height of the left and right subtree for every node. \n// case-1: If both left and right height are same ans will be root.\n// case-2: Else If left height is greater than ans will be root->left.\n// case-3: Ese ans will be root->right.\n\n// 1st solution: TC=O(N)\nclass Solution {\npublic:\n    \n    TreeNode *ans=NULL;\n    int height(TreeNode *root)\n    {\n    if (root == NULL)\n        return -1;\n    else\n    {\n        int lHeight = height(root->left);\n        int rHeight = height(root->right);\n        return 1+max(lHeight,rHeight);\n    }\n }\n \n    void dfs(TreeNode *root)\n    {\n        int lh=height(root->left);\n        int rh=height(root->right);\n        if(lh==rh)\n        {\n            ans=root;\n            return ;\n        }\n        else if(lh>rh)\n        {\n            ans=root->left;\n            dfs(root->left);\n        }\n        else\n        {\n            ans=root->right;\n            dfs(root->right);\n        }\n    }\n    TreeNode* subtreeWithAllDeepest(TreeNode* root) {\n        if(!root) return NULL;\n        if(!root->left && !root->right) return root;\n        dfs(root);\n        \n        return ans;\n    }\n};\n\n// 2nd Solution O(N2)-(worse case)\nclass Solution {\npublic:\n    \n\n    pair<TreeNode*,int> dfs(TreeNode *root)\n    {\n       if(!root) return {NULL,0};\n        if(!root->left && !root->right) return {root,1};\n        pair<TreeNode*,int>left=dfs(root->left);\n        pair<TreeNode*,int>right=dfs(root->right);\n        if(left.second==right.second)\n        {\n            return {root,left.second+1};\n        }\n        else if(left.second>right.second)\n            return {left.first,left.second+1};\n        else\n            return {right.first,right.second+1};\n    }\n    TreeNode* subtreeWithAllDeepest(TreeNode* root) {\n        if(!root) return NULL;\n        if(!root->left && !root->right) return root;\n        pair<TreeNode*,int>ans=dfs(root);\n        \n        return ans.first;\n    }\n};
[]