Binary Search Tree : Lowest Common Ancestor | Editorial by saurabh

Binary Search Tree : Lowest Common Ancestor | Editorial by saurabh_kadian

Trying to list another idea (apart from already mentioned editorial here) which might help in some other questions.

**Intuition:**
- If we have a generic binary tree, we will search both the values and take the binary representation of their paths.
- How to get the binary representation of a path?
    - For every left we take in the path, we add 0 to the path string else we add 1 for a right move.
    - Once we find the desired value we return the path string and propagate the string to the root.
- After getting the binary representation of the two values, we start matching the strings from the root (aka the left side of the path string).
- As soon as we get the first mismatch, we mark the location. Everything we matched up till then represents the path string of the lower common ancestor of the two. 
- Now traverse this path and get the lca node from the root.

**Example:**
Consider the tree
<pre>
10
 |    \
12     14
|    \     |    \
18  5  15  19
|                   \
4                   9
</pre>
Here if want to find the LCA of `18` and `5`, we will find the path strings of both. For `18` it is `00` as we moved left twice from root and for `5` it is `01` as we moved left first and then right.
Now the path for LCA would be to match these as far as we can from the root. The match would result in `0`. This means we have to go left from root once and we get the LCA.
Which here is `12` and which indeed is the LCA of `18` and `5`.

**Quick representation of the intuition:**
```
string get_representation(Node *curr, int value, string rep){
    if(curr->data == value)
        return rep;
    string left = "", right = "";
    if(curr->left != NULL)
        left = get_representation(curr->left, value, rep + '0');
    if(curr->right != NULL)
        right = get_representation(curr->right, value, rep + '1');
    return ((left == "") ? right : left);
}
Node *lca(Node *root, int v1,int v2) {
    // Write your code here.
    string rep_v1 = get_representation(root, v1, "");
    string rep_v2 = get_representation(root, v2, "");
    string lca = "";
    for(int i = 0;i < min(rep_v1.size(), rep_v2.size());++i){
        if(rep_v1[i] != rep_v2[i])
            break;
        lca += rep_v1[i];
    }
    for(int i = 0;i < lca.size();++i)
        root = (lca[i] == '1' ? root->right : root->left);
    return root;
}
```

Binary Search Tree : Lowest Common Ancestor | Editorial by saurabh_kadian

Download submission

All caught up!

View submission

Is your resume even shortlisted?