"🌳🔍 Mastering the Depths: Efficient LCA Search to Rule Them All! | Beats 100% 💯🚀
IntuitionThe goal of the problem is to find the lowest common ancestor (LCA) of the deepest leaves in a binary tree. The LCA of two nodes in a binary tree is th
# Intuition
The goal of the problem is to find the lowest common ancestor (LCA) of the deepest leaves in a binary tree. The LCA of two nodes in a binary tree is the lowest node that is an ancestor of both nodes. To solve the problem, we first need to determine the deepest leaves and then find the LCA of those nodes. This can be done by performing a level-order traversal (breadth-first search) of the tree, identifying the deepest level, and then using the LCA algorithm to find the common ancestor of all nodes at that level.

# Approach
Perform a level-order traversal (BFS) to collect all the nodes at the deepest level of the tree. This is done by iterating through each level of the tree until the queue is empty.

The last set of nodes added to the queue corresponds to the deepest leaves.

Use the lowestCommonAncestor function to find the LCA of all the deepest leaves. Start with the first node in the deepest level and iteratively find the LCA with the subsequent nodes.

Return the LCA of all the deepest leaves.

# Complexity
- Time complexity:
The time complexity is O(N), where N is the total number of nodes in the tree. The level-order traversal visits every node once, and the lowestCommonAncestor function is invoked at most once per pair of nodes.
- Space complexity:
The space complexity is O(N) for the queue used in level-order traversal, where N is the number of nodes in the tree. Additionally, the space required to store the deepest leaves is O(L), where L is the number of nodes at the deepest level.
# Code
```cpp []
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL || root == p || root == q) return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if(left == NULL) return right;
        else if(right == NULL) return left;
        return root;
    }
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        vector<TreeNode*> child;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int n = q.size();
            child.clear();
            while(n--){
                TreeNode *node = q.front();
                q.pop();
                child.push_back(node);
                if(node->left) {q.push(node->left);}
                if(node->right) {q.push(node->right);}
            }
        }
        TreeNode *p = child[0];
        for(int i=1; i<child.size(); i++){
            p = lowestCommonAncestor(root, p, child[i]);
        }
        return p;
    }
};
```
['C++']