CareerCup

I think both of them are O(h), where h is the height of the tree.

BST:
currentnode=root;
While(both nodes are on same side of the currentNode)
{
currentnode= left(or right) child (wherever both nodes are present);
}
return currentnode as answer;

Binary Tree:
Since this would be unsorted, we have to exhaustively do a recursive depth-first-search from root to find a particular node. Remember the nodes traversed to find a node.
Continue, till both the nodes are found.
Then just compare the saved paths from root to nodes, to get the least common parent.

my sol is a vague idea..i wont work if both the nodes are not present in the tree..but u can figure out how to do it

node * findancestor(root , n1 , n2){
  if (!root) return null;
  elseif (root==n1 || root==n2) return root;
  left= findancestor(root->left,n1,n2);
  right= findancestor(root->right,n1,n2);
  if(left && right) return root;
  elseif(left) return left;
  elseif(right) return right;
}

geeksforgeeks.org/?p=1029

public Node leastCommonAncestor(Node root, Node node1, Node node2) {
Element value1 = node1.getValue();
Element value2 = node2.getValue();
Node currentNode = root;
Element value = currentNode.getValue();

while(true) {
if ((value1-value)*(value2-value) <= 0 )
return currentNode;
else if(value1 < value && value2 < value) {
currentNode = currentNode.getLeft();
value = currentNode.getValue();
}
else {
currentNode = currentNode.getRight();
value = currentNode.getValue();
}
}

I do not quite understand the answers here. why everyone does not take the advantage of parent relationship and traverse to root. Keep a record of the route to root and find the minimum acestor using the recorded route

LCA(node *root,node *n1, node *n2)
{ if(n1 is root OR n2 is root) return null ;
else if (n1 ==root->left OR n1 ==root->right) return root;
else if (n2 ==root->left OR n2 ==root->right) return root;
else { LCA(root->left,n1,n2);
LCA(root->right,n1,n2);
}
}

Node *anc;

void getAnc(Node *root, Node *n1, Node *n2) {
if (n1 == n2)
return n1;
else {
bool r1 = FALSE, r2 = FALSE;
anc = NULL;
findAnc(root, n1, n2, &r1, &r2);
}
}

void findAnc(Node *root, Node *n1, Node *n2, bool *r1, bool *r2) {
if (root == NULL)
return;
else if (root == n1) {
*r1 = TRUE;
return;
} else if (root == n2) {
*r2 = TRUE;
return;
}
bool k1 = FALSE, k2 = FALSE, k3 = FALSE, k4 = FALSE;
findAnc(root->left, n1, n2, &k1, &k2);
findAnc(root->right, n1, n2, &k3, &k4);
if (k1 && !k2 && !k3 && k4 || !k1 && k2 && k3 && !k4) {
anc = root;
}
*r1 = k1 || k3;
*r2 = k2 || k4;
return;
}

I think there could be other ways also for doing this problem. Let us assume when you create binary tree, every node has a link to their immediate parent for up traversing.

Algorithm should be:
1. For node n1 find the height of tree which contains nodes till n1. Say h1.
2. For node n2 find the height of tree which contains nodes till n2. Say h2.
3. Find whose height is more h1 or h2 ?
4. For higher height (for example, h2 > h1) node do,
Traverse up the tree to parent node of n2 such that height of n2 equals height of n1. Say, n3 is parent of n2 and equals the height for n1 node.
5. Now, match each parent nodes till root. On success, we find the least common ancestor, Otherwise not.
For example:

while(n3 != n1) {n3 = n3->parent; n1 = n1->parent}

Do a search on BST for the given two values (A,B); the least common ancestor is the node where the two search takes different path, i.e. to search A we have to go down on right-child node and to search B we have to go down on left child-node or vice versa.

The complexity is height of the least common ancestor node and this is the lower bound for this problem.

generally speaking, nodes don't have parent pointers. interviewers will definitely say that.

/* Greatest common ansesotor*/

struct tree * greatestCommonAncestor (struct tree * root, int x, int y)
{
if (!root)
{
return NULL;
}
else
{
if (root->data > x && root->data > y)
{
return greatestCommonAncestor(root->left);
}
else if (root->data < x && root->data < y)
{
return greatestCommonAncestor(root->right);
}
else
return root;
}
}

LEAST COMMON ANCESTOR:

lca( Node a, Node b){ // assuming Node a and b exist in the tree
	lca_h(a, b, root);
}
lca_h( Node a , Node b, Node x){
	if (( a.val<= x.val && b.val>= x.val) || ( a.val>= x.val && b.val <= x.val)){
		return x;
	}
	
	else if ( a.val < x.val && b.val < x.val ){
		lca_h( a, b, x.left);
	}
	
	else if( a.val> x.val && b.val> x.val){
		lca_h(a, b, x.right);
	}
}