C++ - Simple O(n) Solution with BFS+LCA with thought process explained
The thought process goes like this - Find all deepest nodes by traversing the tree using BFS. The required node is nothing but the LCA of all the deepest nodes.
The thought process goes like this - Find all deepest nodes by traversing the tree using BFS. The required node is nothing but the LCA of all the deepest nodes. Finding LCA of all nodes at the same level is equivalent to finding LCA of the `leftMost` and `rightMost` node. Keep track of `leftMost` and `rightMost` nodes while doing BFS and finally return their LCA.\n\n```\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```
[]