PREP67 Editorial

editorial
1

Problem Explanation

We are given a Binary Tree consisting of N nodes and the values of two integers. You have to find the Lowest Common Ancestor (LCA). LCA is defined as the lowest node that both A and B are descendants of.

Approach

We can traverse the tree through DFS and while backtracking back up we can return A if we found A, B if we found B, and the first node that found both. The function called for each node can return the value returned by the subtree containing A or B.

Code

int lowestCommonAncestor(Node* root, int A, int B) {
    if(!root) return -1;
    
    if(root->data==A||root->data==B) return root->data;
    
    int l=lowestCommonAncestor(root->left,A,B);
    int r=lowestCommonAncestor(root->right,A,B);
    
    if(l!=-1&&r!=-1) return root->data;
    
    if(l!=-1) return l;
    return r;
}