Lowest Common Ancestor of Deepest Leaves

Leetcode Problem:

• Lowest Common Ancestor of Deepest Leaves

Summary

• The problem is to find the lowest common ancestor of the deepest leaves in a binary tree.

Approach

• The solution uses a depth-first search (DFS) traversal to find the deepest leaves
• It keeps track of the maximum depth and the nodes at that depth
• Then, it iteratively checks if the nodes at the maximum depth are the deepest leaves by checking if their parent nodes are the same
• If they are, it returns the parent node
• Otherwise, it updates the list of deepest leaves and continues the process until it finds the lowest common ancestor.

Complexity

• O(n), where n is the number of nodes in the tree

Explanation

• The solution uses a recursive DFS traversal to find the deepest leaves
• It keeps track of the maximum depth and the nodes at that depth using a vector
• It also uses a parent array to keep track of the parent nodes of each node
• The traversal function updates the maximum depth and the list of deepest leaves as it traverses the tree
• The lcaDeepestLeaves function iteratively checks if the nodes at the maximum depth are the deepest leaves by checking if their parent nodes are the same
• If they are, it returns the parent node
• Otherwise, it updates the list of deepest leaves and continues the process until it finds the lowest common ancestor.

Solution Code:

/**
 * 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:
    int maxDepth = -1;
    TreeNode* parent[1001];
    vector list;
    void traversal(TreeNode* root, int depth){
        if(root == nullptr) return;
        if(maxDepth < depth){
            maxDepth = depth;
            list.clear();
            list.push_back(root);
        } else if(maxDepth == depth){
            list.push_back(root);
        }
        if(root->left) parent[root->left->val] = root;
        if(root->right) parent[root->right->val] = root;
        traversal(root->left, depth + 1);
        traversal(root->right, depth + 1);
    }
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        traversal(root, 0);
        
        while(true){
            if (list.size() == 1) return list[0];
            vector tmp;
            bool success = true;
            int goal = parent[list[0]->val]->val;
            for(int i = 0 ; i < list.size(); i++){
                tmp.push_back(parent[list[i]->val]);
                if(goal != parent[list[i]->val]->val){
                    success = false;
                }
            }
            if(success) return tmp[0];
            list.clear();
            list = tmp;
        }
        return nullptr;
    }
};