Common Ancestor in a Binary Tree or Binary Search Tree

Binary tree with structure as

struct node {
    int data;
    struct node *left;
    struct node *right;
};

need to find out common ancestor of two nodes.

           [1]
          /   \
       [2]     [3]
      /  \     
    [4]  [5] 
    /    /  \
   [8]  [6]  [7]

say
n1,n2 = 8,3 => Common Ancestor =1
n1,n2 = 8,6 => Common Ancestor =2
n1,n2 = 7,6 => Common Ancestor =5

Method 1)

logic : when traversing from root node,
keep paths for both n1 & n2.
ex1:
p1 : 1,2,4,8
p2 : 1,3
last common value in path is LCA=1
ex2:
p1 : 1,2,4,8
p2 : 1,2,5,6
last common value in path is LCA=2

Algorithm :

FindPath ( root, vector<int> &path, int N )
{
path.push_back(root->key)
if(root->key = N) return 1;
if ( (root->left && findPath( root->left, path, N) ) | |  (root->right && findPath( root->right, path, N) )
    return 1;
path.pop_back(); //if path is not in this subtree
return 0;
}

CommAncsestor( root , n1, n2 ){

vector <int> p1,p2;
int i;

if (!findPath(root, path1, n1) || !findPath(root, path2, n2))
    return -1;

for(i=0; i< path1.size() && i<path2.size(); i++){
   if(path1[i] != path2[i]) break;
   }
return path1[i-1];
}

Method 2)

Now think for a way where
ex:1)
when n1=8, n2=3.
while we call from root =1 , 8 will return from left subtree and 3 will return from right subtree.
so we can say CommonAncestor is 1.

ex:2) n1=8, n2= 6
for previous call, 8 and 6 will be returned from leftsubtree, while in right subtree 6 is not there , hence it will return NULL.
so if one subtree return Null, go and search in similar way as ex:1) in other subtree
so here for
for root=1, Leftsubtree=8, rightsubtree=NULL.
call leftsubtree
root = 2 its leftsubtree return 8, and rightsubtree returns 6. hence Common Ancestor is 2.

struct Node *findLCA(struct Node* root, int n1, int n2)
{
        if (root == NULL) return NULL;
        if (root->key == n1 || root->key == n2)
             return root;

        Node *left_lca  = findLCA(root->left, n1, n2);
        Node *right_lca = findLCA(root->right, n1, n2);

       if (left_lca && right_lca)  return root;

       return (left_lca != NULL)? left_lca: right_lca;
}

FOR Binary Search Tree
Say binary search is as given below

       [7]
      /  \     
    [6]  [9] 
    /    /  \
  [5]  [8]  [10]

n1,n2 = 8,10 => Common Ancestor =9
n1,n2 = 8,6 => Common Ancestor =7
n1,n2 = 5,6 => Common Ancestor =6

as this tree is BST with property that leftSubTree < Parent < RightSubTree
we can use it to get CommonAncsestor.

now as we start traversing from root.
if root < n1 & root < n2 then CommonAncestor lies in Right sub tree of Root.
say in example 1) with 8,10.

if root > n1 & root > n2 then CommonAncestor lies in left sub tree of root
say in example 3) with 5,6

else root itself is CommonAncestor when root < n1 but root > n2. or root > n1 but root < n2
say in example 2) with 6,8.

struct node *CommonAncestor (struct node* root, int n1, int n2)
{
    if (root == NULL) return NULL;
    if (root->data > n1 && root->data > n2)
        return lca(root->left, n1, n2);
    if (root->data < n1 && root->data < n2)
        return lca(root->right, n1, n2);
    return root;
}