CareerCup

node CA(Node root,int key[])
   {
     if(root==null)
     return null;
     int i ;
     for(i=0;i<key.length;i++)
     {
       if(!contain(root.left,key[i])
        break;
     }
     if(i==key.length)
     return CA(root.left,key);

     int j ;
     for(j=0;j<key.length;j++)
     {
       if(!contain(root.right,key[j])
        break;
     }
     if(j==key.length)
     return CA(root.right,key);

     return node;
}

boolean contain(Node root,int key)
{
   if(root==null)
    return false;
   if(root.data==key)
    return true;
   return (contain(root.left,key)||contain(root.right,key));
}

First find the minimum and maximum element in the list of n nodes, and then apply standard LCA solution to min & max nodes.

Dont we need two nodes or therir key velues of which we have to find the common ancestor???

Abran - Where did u have u r interview?? Bangalore??

Can we search in bottom-up fashion as the node that we hit first as ancestor of all the keys will indeed be the least common ancestor? The same may not be the case when we search top down.

import java.util.List;

public class Lca {
	private static class Node {
		Node left;
		Node right;
	}

	private Node root;

	// Helper class
	private static class LcaSpec {
		Node lca;
		int numOfChildren;

		LcaSpec(Node lca, int numberOfChildren) {
			this.lca = lca;
			this.numOfChildren = numberOfChildren;
		}
	}

	// Gets the spec of its children.
	// Checks if one of its child is already an lca.
	// Checks if it is one of the nodes (uses naive reference equals) and
	// updates spec.
	//
	// Recursive and O(N x M)
	// N - size of tree
	// M - size of list of child nodes
	private LcaSpec getLca(Node node, List<Node> nodes) {
		if (node == null) {
			return null;
		}
		LcaSpec leftSpec = getLca(node.left, nodes);
		LcaSpec rightSpec = getLca(node.right, nodes);
		if (leftSpec != null && leftSpec.numOfChildren == nodes.size()) {
			return leftSpec;
		}
		if (rightSpec != null && rightSpec.numOfChildren == nodes.size()) {
			return rightSpec;
		}
		int numOfChildren = (leftSpec == null) ? 0 : leftSpec.numOfChildren;
		numOfChildren += (rightSpec == null) ? 0 : rightSpec.numOfChildren;
		if (nodes.contains(node)) {
			++numOfChildren;
		}

		return new LcaSpec(node, numOfChildren);
	}

	// Get LCA given list of child nodes.
	// Assumption is there exists such a node.
	public Node getLca(List<Node> nodes) {
		return getLca(root, nodes).lca;
	}
}

1. For each node (in the multiple node list) store its path from root to itself say each path in an array. This can be done by pre - order search. Remember this not a BST.
2. Let A,B,C,.. M be such arrays. (count m).
3. Let n be the shortest of the above paths. you can also collect the arrays that yield the shortest paths.
for (i=0; i<n;i++)
{
if( i is not within the range of any one Array Say H)
{
then last element of H is the LCA;
break;
}

if(A[i] == B[i] == ... == M[i]);//great do nothing
else
{
A[i-1] is the LCA.
break;
}
}

node *closest(node* root, mynode* p, mynode* q)
{
mynode *l, *r, *tmp;

if(root == NULL)
{
return(NULL);
}

if(root->left==p || root->right==p || root->left==q || root->right==q)

{
return(root);
}
else
{
l = closest(root->left, p, q);
r = closest(root->right, p, q);

if(l!=NULL && r!=NULL)
{
return(root);
}
else
{
tmp = (l!=NULL) ? l : r;
return(tmp);
}
}
}

<pre lang="" line="1" title="CodeMonkey38495" class="run-this">mynode *closestAncestor(mynode* root, mynode* p, mynode* q)
{
mynode *l, *r, *tmp;

if(root == NULL)
{
return(NULL);
}

if(root->left==p || root->right==p || root->left==q || root->right==q)

{
return(root);
}
else
{
l = closestAncestor(root->left, p, q);
r = closestAncestor(root->right, p, q);

if(l!=NULL && r!=NULL)
{
return(root);
}
else
{
tmp = (l!=NULL) ? l : r;
return(tmp);
}
}
}



</pre><pre title="CodeMonkey38495" input="yes">
</pre>

static BinaryNode leastCommonAncestor(BinaryNode root,List<Integer> integers){
		
		if(root == null) return null;
		for (Iterator<Integer> iterator = integers.iterator(); iterator.hasNext();) {
			Integer value = iterator.next();
			if(value == root.value)
				return root;
		}
		
		BinaryNode lnode = leastCommonAncestor(root.left, integers);
		BinaryNode rnode = leastCommonAncestor(root.right, integers);
		
		if(lnode == null && rnode == null) return null;
		if(lnode != null && rnode != null) return root;
		
		if(lnode != null) return lnode;
		else return rnode;
		
		
	}

As everybody has written code, The algorithm for finding the LCA in simple words is as follows:
Start from root (TOP: preorder traversal) . lets consider the 2 nodes given as input be n1 and n2. Search both the left and right subtree of the root. As long as you find both n1 and n2 being part of one of the subtree, drillAs we proceed from root towards the leafAs we proceed from root towards theAs we proceed from root towards the leaf leafAs we proceed from root towards the leafAs we proceed from root towards the leafAs we proceed from root towards the leaf down on that subtree ignoring the other. If you find a node such that n1 is in left subtree and n2 in right subtree or vice versa then it will be the LCA.