CareerCup

easy...same as linked list intersection problem.

traverse upwards from both the nodes using parent pointer and find the distance to the root

say d1 > d2

traverse n1 upwards, d1-d2 times...by keeping n2 at same position

now traverse both upwards and they reach at LCA.

/************************************
node1 - first node
node2 - second node
Designed for BT not BST
************************************/
node Reachability(node subroot, node node1, node root)
{
	node current_node = node1;
	while(current_node != root)
	{
		if(current_node == subroot)
			return current_node;
		else
			current_node = current_node.parent;
	}
	if(current_node == subroot)
		return current_node;
	else
		return null;
}

node LCA(node root, node node1, node node2)
{
	node LCA = Reachability(node1, node2, root);
	while(LCA == null && node1 != root)
	{
		node1 = node1.parent;
		LCA = Reachability(node1, node2, subroot);
	}
	return LCA;
}

node LCAMain(node root, node node1, node node2)
{
	node LCA1 = LCA(root, node1, node2);
	node LCA2 = LCA(root, node2, node1);
	
	node finalLCA = Reachability(LCA1, LCA2, root);
	if(finalLCA != null)
		return finalLCA;
	return(finalLCA = Reachability(LCA2, LCA1, root));	
}

here is my solution, l implemented d same logic which siva has mentioned above.
public class LowestCommonAncestor {

/**
* Given a TNode with following special property, develop an algorithm to
* find the LCA of two input nodes. Only O(1) variables can be used.
* property - all nodes have information only about their parents not their children
*/
public static void main(String[] args) {
// lets create a TNode
TNode root = new TNode(100);
TNode t1 = new TNode (80); TNode t2 = new TNode(75);
t1.parent = root; t2.parent = root;

TNode t3 = new TNode (70); TNode t4 = new TNode(90);
TNode t5 = new TNode(60); TNode t6 = new TNode(50);

TNode t7 = new TNode (40); TNode t8 = new TNode(30);
TNode t9 = new TNode(20); TNode ta = new TNode(10);
TNode tb = new TNode (15);



t3.parent = t1; t4.parent = t1;
t5.parent = t3; t6.parent = t3;
t7.parent = t5; t8.parent = t5;t9.parent = t6; ta.parent = t6;
tb.parent = t7;

TNode lca = findLCA(ta,tb);
System.out.println(lca.v);
}

public static TNode findLCA(TNode n1,TNode n2){
int d1 = 0;
int d2 = 0;

TNode e1 = n1;
TNode e2 = n2;

d1 = getDepth(e1);
d2 = getDepth(e2);

int d = 0;
e1 = n1;
e2 = n2;
if(d2 > d1) // n2 will move d2-d1
{
d = d2 -d1;
e2 = traversNode(e2, d);
}else if (d1 > d2){
d = d1 - d2;
e1 = traversNode(e1, d);
}
while(e1 != e2){
e1 = e1.parent;
e2 = e2.parent;
}
return e1;

}

public static int getDepth(TNode n){
int d = 0;
while(n.parent != null){
n =n.parent;
d++;
}
return d ;
}

public static TNode traversNode(TNode n, int d){
while(d > 0)
{
n = n.parent;
d --;
}
return n;
}

}
class TNode{ // NOT a BST
TNode parent;
int v;

TNode(int v){
this.v = v;
this.parent = null;
}

}

The easiest way should be to use a list/vector of parents of first node traversing consecutively to root (parent null)

Then repeat traverse for next node till the current parent is found in vector from back
This will only take 2 traverses

else we can use siva's height diff method with extra check where the other shallower node could be ancestor of the deeper node this will need 3 passes -from leaf to root twice and leaf to LCa

The recursive way will fail if one node is grandparent of second!

//
1. we can calculate the depth of both the given nodes, and let us suppose it is d1 and d2.
2. let us take the abs(d1-d2) into int type variable difference.
3. suppose d1 is greater than d2, than move up the parent chain till the count reaches to the value of difference from the node of depth d1.
4. Now both the nodes are at same depth. start moving in parallel till both the nodes point to the same parent.

we can calculate depth in log(n) time if tree is balanced. then getting diff is constant time, and again we move at max log(n) times from the node of greatest depth to the root.

We have provided with the node-parent information. How about using this information, somewhat like following:

findLCA(u,v)
{
if(u==v)
  return p[u];
if(p[u]==p[v])
  return p[p[u]];
if(u==p[v])
  return p[u];
if(v==p[u])
  return p[v];
return FindLCA(p[u],p[v]);
}