CareerCup

Find the predecessor for both the nodes, considering that the left subtree for both of these nodes is null.
The first common predecessor of both of these nodes will be the common ancestor.

start looking for the node whose value lie between given two node ....that node will be common ancestor

Node leastCommonAncestor(Node root, Node left, Node right)
{
	if(root == null || p == null || q == null)
		return null;
	if(p == root || q == root)
		return root;
	Node left = LCA(root.left, p, q);
	Node right = LCA(root.right, p, q);
	if(left != null && right != null) return root;
	else
		return left != null ? left : right;            
}

// Assuming distinct elements. in the tree.
int findCommonAncestor(int first, int second, node root,node** ans ){
   int l,k;
   if(root == null)
       return 0;
   if( root == first){
      l = 1; // for 1st
   else if(root == second)
       l = 2;// for 2nd
   

   int k = findCommonAncestor(first, second, root->left);
   if( k == 3){
      everything from child. (or) child could have updated ans.
       return 3;
   }
   else if( l+k == 3){
      the current node is common ancestor.
       *ans == root;
       reutrn 3;
   }
   else{
       int k =findCommonAncestor(first, second, root->right);
       if( k == 3){
           everything from child. (or) child could have updated ans.
           return 3;
       }
       else if( l+k == 3){
           the current node is common ancestor.
           *ans == root;
           reutrn 3;
       }
       else{
           return l+k;
       }
   }
}

For a general binary tree, to find LCA, we can find path of each node from the root and store them in two arrays. Next we find the last common element in both the arrays.
Would this work?

Node LowestCommonAncestor( Node root, int value1, int value2 )
{
while( root != null )
{
int value = root.getValue();
if( value > value1 && value > value2 )
root = root.getLeft();
else if( value < value1 && value < value2 )
root = root.getRight();
else
return root;
}
return null;
}

Finding LCA for two nodes is totally different from finding LCA for two values. Later is much easier.

Algorithm for finding LCA for two values:
The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). if you find a node with value in between n1 and n2 then n is the LCA
Basically just do BSF the compare the value (n2<A.value<n1)
BST implementation is much straightforward, if it is other type of tree for example not sorted multiple child nodes we have to take some assumptions. The algorithm would be very different. So context is first thing we should clear up.

Assume it is a BST,

Node findLCA(Node root, int v1, int v2){

Queue queue = new Queue();
Queue.enque(root);

While(queue.size()>0)
{
Node current = queue.deque();

If(v2<current.value<v1)
Return current;

If(current.left!=null)
Queue.enque(current.left);

If(current.right!=null)
Queue.enque(current.right);


}


}

Finding LCA for two nodes, it does not matter if it is BST or not.

Do a bottom up traversal and record the full path from searched node to root, assume we do not have circular references . use LinkedList to record full path so we keep the insertion order, then result would be the first elements of intersection of two paths .

Node findLCA(Node node, Node n1, Node n2)
{
LinkedList pathNode1 = new LinkedList();
LinkedList pathNode2 = new LinkedList();

findFullPathForNode(root, n1, pathNode1);
findFullPathForNode(root, n2, pathNode2);

//keep the same node;
pathNode1.retainAll(pathNode2);

if(pathNode1.size()>0)
return pathNode1.first();
}

findFullPathForNode(Node current, Node n1, LinkedList path){
if(current==null)
return;

path.add(current);
//find the target node
if(current == n1){
return;
}

findFullPathForNode(current.left, n1, path);
findFullPathForNode(current.right, n1, path);

}

public static TreeNode firstAncestor(TreeNode root, TreeNode a, TreeNode b) {
		Stack<TreeNode> path1 = new Stack<TreeNode>();
		Stack<TreeNode> path2 = new Stack<TreeNode>();
		
		pathToRoot(root, path1, a);
		pathToRoot(root, path2, b);
		
		for (TreeNode node : path1) {
			System.out.print(node.data + " ");
		}
		System.out.println();
		for (TreeNode node : path2) {
			System.out.print(node.data + " ");
		}
		System.out.println();
		path1.retainAll(path2);
		if (path1.size() > 0) {
			return path1.get(path1.size() - 1);
		}
		return null;
	}

	public static boolean pathToRoot(TreeNode root, Stack<TreeNode> paths,
			TreeNode target) {
		if (root == null) {
			return false;
		}
		paths.push(root);
		if (root.data == target.data) {
			return true;
		}
		if (root.left != null) {
			if (pathToRoot(root.left, paths, target)) {
				return true;
			}
		}
		if (root.right != null) {
			if (pathToRoot(root.right, paths, target)) {
				return true;
			}
		}
		paths.pop();
		return false;
	}

we can do it in some optimized way like , say a and b given two node.

first compare a and b with rooth node
if root node is greater than a & b move to left subtree
if root node is lesser than a & b move to right subtree
if root node is greater than one and lesser than another : then return root node as first common ancesstor.

we can keep these in recursion.

and we have to test for some other condition like a is parent of b or vice versa .

Please let me know , how far i am correct and how to opimized it further ?

node *lca(node *root, node *a, node *b) {
  if(root==null)
    return null;
  if(node==a||node==b)
    return node;
  node *left=lca(node->left);
  node *right=lca(node->right);
  if(left && right)
    return node;
  if(left)
    return left;
  else
    return right;
}