Simple DFS solution || O(N)time || BFS+LCS
\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 *     TreeNod
\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 */\n\n //idea is find all nodes in last level & then find the least common ancestor for extreme left node & extreme right node.\nclass Solution {\npublic:\n    TreeNode* lca( TreeNode* root, TreeNode* p, TreeNode* q ) {\n        if ( !root || root == p || root == q ) return root;\n        TreeNode *left = lca( root->left, p, q );\n        TreeNode *right = lca (root->right, p, q );\n\n        return !left? right: !right? left: root;\n    }\n    \n    TreeNode* subtreeWithAllDeepest(TreeNode* root) {\n        if ( !root || !root->left && !root->right ) return root;\n        TreeNode *leftMost = NULL;\n        TreeNode *rightMost = NULL;\n        \n        queue<TreeNode*> q;\n        q.push(root);\n        while( !q.empty() ) {\n            int levelSize = q.size();\n            for(int level = 0; level < levelSize; level++ ) {\n                TreeNode* node = q.front(); q.pop();\n                if ( level == 0 ) leftMost = node;\n                if ( level == levelSize - 1 ) rightMost = node;\n                \n                if (node->left) q.push(node->left);\n                if (node->right) q.push(node->right);\n                \n            }\n        }\n        return lca( root, leftMost, rightMost );\n    }\n};\n\n```
['Breadth-First Search', 'C++']