C++✅✅ || Easiest solution using BFS || Beats 90%
Intuition\n Describe your first thoughts on how to solve this problem. \nMy approach was to perform BFS and store only the first and last node at the deepest le
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nMy approach was to perform BFS and store only the first and last node at the deepest level.\n\nFind the LCA of first and last node.\n\nThus it is ensured that all the other nodes between the first and last node will be part of the LCA found.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe first use BFS, i.e., Level Order Traversal on the tree and find out the first and last nodes of the deepest level. Then we return their lca using the standard recursive procedure. Although, it is a two pass solution, it\'s really easy to understand how it works\n# Complexity\n- Time complexity:O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\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), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    TreeNode* subtreeWithAllDeepest(TreeNode *root) {\n        queue<TreeNode*> q;\n        q.push(root);\n        TreeNode *first, *last;\n        while(!q.empty()) {\n            first = q.front(); last = q.back();\n            int sz = q.size();\n            while(sz--) {\n                auto node = q.front(); q.pop();\n                if(node -> left) q.push(node -> left);\n                if(node -> right) q.push(node -> right);\n            }\n        }\n        return lca(root, first, last);\n    }\n    \n    TreeNode* lca(TreeNode *root, TreeNode *p, TreeNode *q) {\n        if(!root || root == p || root == q) return root;\n        auto left = lca(root -> left, p, q);\n        auto right = lca(root -> right, p, q);\n        return left ? right ? root : left : right;\n    }\n};\n```
['Tree', 'Breadth-First Search', 'C++']