CareerCup

/* Function to find LCA of n1 and n2. The function assumes that both 
   n1 and n2 are present in BST */
struct node *lca(struct node* root, int n1, int n2) 
{ 
    if (root == NULL) return NULL; 
  
    // If both n1 and n2 are smaller than root, then LCA lies in left 
    if (root->data > n1 && root->data > n2) 
        return lca(root->left, n1, n2); 
  
    // If both n1 and n2 are greater than root, then LCA lies in right 
    if (root->data < n1 && root->data < n2) 
        return lca(root->right, n1, n2); 
  
    return root; 
}

(let i and j be the given nodes)

- reverse the graph
- perform a BFS from 'i' keeping track of the layer/level where the other nodes are discovered (let Ki denote the distance of node K from i)
- perform a similar BFS from 'j', collecting Kj for every node K in the graoh

at this point, the shortest distance (in hops) from every node to nodes 'i' and 'j' is known

min(abs(Ki - Kj)) for every node K will give the K that is the least common ancestor