is the node typical sturcuture with left and right? or some other representation?

node* LCA(node* root, node* nd1, node* nd2){

if(root==NULL)
return NULL;

if(root->left==nd1 || root->right==nd1 || root->left==nd2 || root->right==nd2)
return root;

node* lc = LCA(root->left,nd1,nd2);
node* rc = LCA(root->right,nd1,nd2);

if(lc!=NULL && rc!=NULL)
return root;

if(lc==NULL) return rc;
else return lc;
}

Yes, typical binary tree - each node has a left and right node pointer, as well as a pointer to it's parent.

Anonymous - you cannot take as a parameter the root.

My solution (after being told that I cannot store each parent in a hash table was to raise the lower of the 2 nodes to the level of the other node, and traverse up the tree until r->parent == l->parent)

sorry it should have been ...

node* LCA(node* nd, node* nd1, node* nd2){

if(nd==NULL)
return NULL;

if(nd->left==nd1 || nd->right==nd1 || nd->left==nd2 || nd->right==nd2)
return nd;

node* lc = LCA(nd->left,nd1,nd2);
node* rc = LCA(nd->right,nd1,nd2);

if(lc!=NULL && rc!=NULL)
return nd;

if(lc==NULL) return rc;
else return lc;
}

and call
node* parent = LCA(root, nd1, nd2);

another one:-
Node * LCA(Node *t , Node *n1,Node * n2)
{
if (!t) return NULL ;

if ((n1->val < t->val)) && (n2->val < t->val))
return LCA(t->left,n1,n2);

if ((n1->val > t->val)) && (n2->val > t->val))
return LCA(t->right,n1,n2);

if ( (n1->val <= t->val)) && (n2->val >= t->val))
return t;
}

Remember - you only have node1 and node2 at the start. Each node contains a reference to the parent, so you can get the root by traversing to the root, but you start out with only node1 and node2.

node* LCA(node* nd1, node* nd2){

node* cur1 = nd1;
node* cur2 = nd2;

// calculate nd1 height
int nd1_height = 0;
while(cur1->parent!=NULL){
nd1_height++;
cur1 = cur1->parent;
}

// calculate nd2 height
int nd2_height = 0;
while(cur2->parent!=NULL){
nd2_height++;
cur2 = cur2->parent;
}

int diff = nd1_height - nd2_height;

cur1 = nd1;
cur2 = nd2;

if(diff>0){
while(diff--){
cur1 = cur1->parent;
}
} else{
diff = -diff;
while(diff--){
cur2 = cur2->parent;
}
}

while(1){
if(cur1==NULL || cur2==NULL) break;
if(cur1 == cur2)
return cur1;
cur1 = cur1->parent;
cur2 = cur2->parent;
}

return NULL;
}

while calculating the height of node1 and node2...we can check if the other node comes on the way to the root...if yes then return that immediatley...

Google tarjan's offline LCA algorithm

People really misguide and confuse. The question clearly states its not a BST, but lot of people have given solution assuming its a BST. Its easy to do in a BST.

also i see another solution that talks about parent pointer. Does a normal binary tree have parent pointer ? no is the clear answer.

So the solution should be for a Binary Tree (not BST) , (of course that can be unbalanced, and incomplete)), which means there is only a left and right pointer. No parent or up, no rule that left should be less than parent and right greater than parent. - so a simple binary tree.

Somehow people have byhearted solutions and they dump that in interviews and they get selected.

Since we are not allowed to store the nodes in a DS, the first thing that comes to my mind is the traversals. We can find the common root from two traversals.

Construct the preorder and inorder traversals. The common root is the one which has the follg two properties:
a) Should be present in between the two nodes in the inorder traversal
b) If there is more than one in a), then the common root is the one which occurs the left-most in the pre-order traversal.

We need not store the nodes per se in the DS but just their values from the traversals in say a array/vector...I believe thats allowed...

How about this- travel along the path from one of the 2 nodes to the root, and check each time if the other node occurs in the other subtree, i.e., if current node is left child, check the right child subtree or vice-versa.

Let the nodes be (a,b)

findLca( Node *a, Node *b )
{
bool found = false;
Node *p = findParentOf( a );

//try finding b in the tree rooted at p->left
if ( findNodeIn( b, p->left ) ) {
return p;
}
Node *otherSubTree = p->right;

// the other node has to be in otherSubTree
// or a subtree of an ancestor of p, unless
// the other node is p itself, in which case
// return its parent
while ( 1 ) {
if ( findNodeIn( b, otherSubTree ) ) {
return p;
}

// Here we know LCA is either p or
// in a subtree of p's ancestor
Node *newP = findParentOf( p );
if ( !newP || p == b ) {
return newP;
}
if ( p == newP->left ) {
otherSubTree = newP->right;
}
else {
otherSubTree = newP->left;
}
p = newP;
}
}

Why do people get carried away and give all kind of weirdo answers! and half of the page long codes dont make any sense without description. Please avoid doing that.

Coming to the problem. We know that root is not given and it is not a BST. But one thing is that it has pointer to the parent.

*This problem is similar to finding the intersection of two linked lists*.
Now use the same logic of finding the intersection of two linked lists here and find it. you would get it.

LCA(*node A, *node B){
  *node t1 = A;
  *node t2 = B;


while (t1 != t2){    
    if (t2->parent == null)
       if (t1-> parent == null)
          return NoCommonParent
       else
          t1 = t1->parent;
    else
       t2=t2->parent;
  }
  return t1;

}

node* LCA(node* root, int a, int b)
{
if (!root || root->data == a || root->data == b)
return NULL;

node* lcaNode = NULL;
int tmp = findLCA(root, a, b, &lcaNode);
return lcaNode;
}

int findLCA(node* root, int a, int b, node** lcaNode)
{
if (!root)
return 0;
int l = findLCA(root->left, a, b, lcaNode);
int r = findLCA(root->right, a, b, lcaNode);

if (l + r == 2)
{
if (*lcaNode == NULL)
{
*lcaNode = root;
}
return 2;
}
else
{
return l + r + ((root->data == a) || (root->data == b) ? 1 : 0);
}
}

Properties:
1. Binary tree. not necessarily BST.
2. No parent node;

---code---

class Ancestor{
	static Node leftNode,rightNode;
	static String leftCode,rightCode;
	static private void inorderTraversal(Node n, String code){
	  if(n==leftNode)
		leftCode=code;
	  
	  if(n==rightNode)
		rightCode=code;
	 
	  if(n.left!=null)
		inorderTraversal(n.left,code + "0");


if(n.right!=null)
		inorderTraversal(n.right,code + "1");
	   
	}

static public Node findCommonAncestor(Node root, Node left, Node right){
	  leftNode=left; rightNode=right;
	  inorderTraversal(root,""); //empty string
	  Nodeparent=root;
	  for(int i=0;i<leftCode.length&&i<rightCode.length;i++)
	  {
		 if(leftCode.charAt(i)!=rightCode.charAt(i))
		   break;
		 else{
		   if(leftCode.charAt(i)=='0')
			   parent = parent. left;
		   else
			   parent = parent. right;
		 }
	  }
	  if(i==leftCode.size()||i==rightCode.size())
		 return null;
	  else
		 return parent;
	}
}