CareerCup

Isn't this problem the same as finding intersection point of two linked list?

P -> ......> Root
Q -> .... > Root

Find depth of P & Q p,q

diff = p-q;

Return the LCA which is the abs(diff) from longer list.

Very easy using link from child to parent. Create the ordered list of ancestors for node q. Then check inclusion of any parent of p on the way up to the root. The first parent of p included in the list is the LCA.

public class Node {
private Node parent;
private Integer value;

public Node(Integer value) {// constructor for root
this.value = value;
}

public Node(Node parent, Integer value) {
this(value);
this.parent = parent;
}

public Node lcs(Node other) {
LinkedList<Node> parents = other.getParents();
return this.findLCA(parents);
}

private Node findLCA(List<Node> parents) {
Node parent = this.parent;
while (parent != null) {
if (parents.contains(parent)) {
return parent;
} else {
parent = parent.parent;
}
}
return parent;
}

private LinkedList<Node> getParents() {
if (parent == null) // / tree root
return new LinkedList<Node>();
else {
LinkedList<Node> parents = this.parent.getParents();
parents.addLast(this.parent);
return parents;
}
}
}

----
public class LCASample {
public static void main(String[] args) {
Node n1 = new Node(1);
Node n2 = new Node(n1, 2);
Node n3 = new Node(n1, 3);
Node n4 = new Node(n2, 4);
Node n5 = new Node(n2, 5);
Node n6 = new Node(n4, 6);
Node n7 = new Node(n5, 7);
Node n8 = new Node(n5, 8);
Node n9 = new Node(n8, 9);
System.out.println(n6.lcs(n9).getValue());
}
}

Your solution requires additional storage. I gave a simpler solution using recursion as follows:

Node* LCA (Node *p, Node *q){
if(p == q)
return p;
else{
if(p->parent !=null)
LCA(p->parent,q); //move p up one level
else if (q->parent !=null)
LCA(p,q->parent); //move q up one level
else
return NULL; //no common ancestor
}
}

Complexity : Worst case is O(n)

Node * LCA(Node * p, Node * q)
{
	while(p && q && p!=q)
	{
		if(p->parent != q && q->parent != p)
		{
			p = p->parent;
			q = q->parent;
		}
		else if(p->parent == q)
		{
			p = p->parent;
		}
		else if(q->parent = p)
		{
			q = q->parent;
		}
	}
	if(p && q && p==q)
	{
		return p;
	}
	else
	{
		return NULL;
	}
}

Let each node have a visited flag set to 0 by default.

On each pass , 2 nodes traverse one level up till they reach root and mark visited = 1 if its zero. If visited flag == 1 before the node sets it, that is the LCA

travel one time to the root for both nodes to find their depths. move the lover till they are at same level. then move both together until parent is same. o(log n) for balanced tree O(n) for the rest