c++ (clean code) ✅✅ || using DFS || beats 100% time
Approach\n\n\n\n\n- Go down while calculating the depth.\n    \n        int l = subtree(root->left, c+1);\n        int r = subtree(root->right, c+1);\n\n- If de
# Approach\n\n![Screenshot 2024-04-20 024834.png](https://assets.leetcode.com/users/images/621d64dc-302c-40c0-90d5-718afa5fff34_1713561529.5758123.png)\n\n\n- Go down while calculating the depth.\n    ```\n        int l = subtree(root->left, c+1);\n        int r = subtree(root->right, c+1);\n    ```\n- If depth+leftHeight == depth+rightHeight, here we get a valid node which could be our finalans\n    ```\n        if(c+l == c+r) {\n            if(maxh<=c+l) {\n                ans = root;\n                maxh=c+l;\n            }\n        }\n    ```\n- Update maxh when new height obtained is greater than maxh\n\n\n# Complexity\n\n```\nTime complexity: O(N)\n```\n```\nSpace complexity: O(N)\n```\n\n# Code\n```\nclass Solution {\npublic:\n\n    TreeNode* ans;\n    int maxh;\n    int subtree(TreeNode* root, int c) {\n        if(!root) return 0;\n        int l = subtree(root->left, c+1);\n        int r = subtree(root->right, c+1);\n        if(c+l == c+r) {\n            if(maxh<=c+l) {\n                ans = root;\n                maxh=c+l;\n            }\n        }\n        return 1+max(l,r);\n    }\n\n    TreeNode* subtreeWithAllDeepest(TreeNode* root) {\n        maxh=0;\n        subtree(root,1);\n        return ans;\n    }\n};\n```\n\n```\nif(helpful) Upvote++ ;\n\uD83D\uDC4D\uD83D\uDC4D\uD83D\uDC4D\uD83D\uDC4D\n```
['Tree', 'Depth-First Search', 'Binary Tree', 'C++']