C++ | Most Unique Approach | O(n) ONLY 100% Faster | With Explanations
We will use a pair in the solution.\nThe first part of the pair will contain the node and the second part will contain the deepest level.\nAt base condition we 
We will use a pair in the solution.\nThe first part of the pair will contain the node and the second part will contain the deepest level.\nAt base condition we will return a pair as ```{NULL, -1}```. \n\nAt every position in the tree we will check the deepest level i.e., ```pair.second``` of left and right subtree.\n\nNow there are 2 cases possible here:\n1. deepest level of right and left subtree is same i.e., ```l.second == r.second``` - This means that the current node is the subtree having the deepest nodes. Thus, we will return a pair having ```p.first = root (current node)```. Now, how to ensure that it is the deepest subtree? simple answer is to set its level as ```l.second + 1``` or ```r.second + 1``` and return it. How it is working takes us to the second condition.\n\n2. Now let us assume we get left and right subtrees with different levels. In this case, we will return the pair of subtree with deeper level but will increment its level by 1. \n\nNow, from 1st condition we got a subtree having the deepest nodes and we are always incrementing it\'s level by 1. **So, no matter what if we even get another subtree whose level is lesser than the one which is deepest it will not be returned. And if we get another subtree whose level is deeper it will be retuned due to 2nd condition and if they both have same deepest level, we will return that subtree instead**.\n\nNow, this algorithm also ensures that only a **complete subtree is being returned due to the 1st condition**.\n\n\n```\n\t// pair.first = node\n    // pair.second = deepest level\n    \n    pair<TreeNode*, int> deepest(TreeNode* root) {\n        if(!root) return {NULL, -1};\n\t\t\n        pair<TreeNode*, int> l = deepest(root->left), r = deepest(root->right), p;\n        \n        if(l.second == r.second) { \n            p.second = l.second + 1;\n            p.first = root;\n            return p;\n        }\n        \n        if(l.second > r.second) {l.second += 1; return l;}\n        else {r.second += 1; return r;}\n    }\n    \n    TreeNode* subtreeWithAllDeepest(TreeNode* root) {\n        pair<TreeNode*, int> p = deepest(root);\n        return p.first;\n    }\n```
['Tree', 'Depth-First Search', 'Breadth-First Search', 'Binary Tree']