Common Ancestor in a Binary Tree or Binary Search Tree

We need to find a Least Common Ancestor of Two given nodes in Binary tree.

            [1]
          /    \ 
       [2]      [3]
      /  \      /  \
    [4]  [5]  [9] [10]
    /    /  \ 
  [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;
}

Working Code can be Found at http://ideone.com/J7gzfk
Least Common Ancestor LCA of 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 CommonAncestor(root->left, n1, n2);
    else if (root->data < n1 && root->data < n2)
        return CommonAncestor(root->right, n1, n2);
    return root;
}

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

// A recursive C program to find LCA of two nodes n1 and n2 By Gohired.in 
#include <stdio.h>
#include <stdlib.h>

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

struct node *commonAncestor2(struct node* root, int n1, int n2)
{
    while (root != NULL)
    {
        if (root->data > n1 && root->data > n2)
           root = root->left;
 
        else if (root->data < n1 && root->data < n2)
           root = root->right;
 
        else break;
    }
    return root;
}

struct node *commonAncestor(struct node* root, int n1, int n2)
{
	if (root == NULL) return NULL;
	if (root->data > n1 && root->data > n2)
		return commonAncestor(root->left, n1, n2);

	else if (root->data < n1 && root->data < n2)
		return commonAncestor(root->right, n1, n2);

	return root;
}

struct node* newNode(int data)
{
	struct node* node = (struct node*)malloc(sizeof(struct node));
	node->data = data;
	node->left = node->right = NULL;
	return(node);
}

int main()
{
	struct node *root	 = newNode(20);
	root->left			 = newNode(8);
	root->right			 = newNode(22);
	root->left->left		 = newNode(4);
	root->left->right	 = newNode(12);
	root->left->right->left = newNode(10);
	root->left->right->right = newNode(14);

	int n1 = 10, n2 = 14;
	struct node *t; 
	t = commonAncestor(root, n1, n2);
	printf("LCA of %d and %d is %d \n", n1, n2, t->data);

	n1 = 14, n2 = 8;
	t = commonAncestor(root, n1, n2);
	printf("LCA of %d and %d is %d \n", n1, n2, t->data);

	n1 = 10, n2 = 22;
	t = commonAncestor(root, n1, n2);
	printf("LCA of %d and %d is %d \n", n1, n2, t->data);
	printf("------Out put with Iterative Mehtod --------\n");
	
	n1 = 10, n2 = 14;
	t = commonAncestor2(root, n1, n2);
	printf("LCA of %d and %d is %d \n", n1, n2, t->data);

	n1 = 14, n2 = 8;
	t = commonAncestor2(root, n1, n2);
	printf("LCA of %d and %d is %d \n", n1, n2, t->data);

	n1 = 10, n2 = 22;
	t = commonAncestor2(root, n1, n2);
	printf("LCA of %d and %d is %d \n", n1, n2, t->data);
	getchar();
	return 0;
}