CareerCup

node LCA(node *root, node *n1, node * n2) {
if ( root == null ) return root;
if ( n1 == null ) return n2;
if ( n2 == null ) return n1;
if (( n1->value < root->valule ) && ( n2->value > root->value )) return root;
if (( n1->value > root->valule ) && ( n2->value < root->value )) return root;
if (( n1->value < root->valule ) && ( n2->value < root->value )) return LCA(root->left, n1,n2);
if (( n1->value > root->valule ) && ( n2->value > root->value )) return LCA(root->right, n1,n2);
}

Start searching for both the nodes from the root.
The first node where the search path diverges is the LCA.
By divergence, i mean one value is less than the node and other is greater

Least common Ancestor is that node form which one of the node is on left side and other is right side.
so start searching the node from top s.t n >= first and n <= second.
For any intermediary node, the case would be n > both or n< both.
accordingly go to the right or left child.

It seems that there is duplicate question. Some someone has given a very good simplification about this problem. Can't remember whom it is. Basically it can be taken as two link lists. A --> TOP and B --> TOP, then this problem can be regards as if these two link list merge at some node.

public int getHeight(Node n){
int h=0;
while(n!=null){
n = n.parent;
h++;
}
return h;
}
public LCA(Node p,Node q){

int h1 = getHeight(p);
int h2 = getHeight(q);
if(h1>h2){
swap(h1,h2);
swap(p,q);
}
int diff = h2-h1;
for(i=0;i<diff;i++){
q = q.parent;
}
while(p!=null & q!=null{
if(p==q){
return p;
} else{
p=p.parent;
q=q.parent;
}
}
}

private Node LCA_Normal(Node root, int a, int b){
	if(root==null){
		return null;
	}
	if((root.data>a && root.data<b)||(root.data<a && root.data>b)) {
 		return root;
	}
	if(root.data>a && root.data>b) {
		return LCA_Normal(root.left,a,b);
	}
	if(root.data<a && root.data<b) {
		return LCA_Normal(root.right,a,b);
	}
	return root;
}

Complexity -- O(logn)