CareerCup

1.start with the root value
2.(BST property)find the node that is in between the value 1 and value 2 by traversing
node BST(rootnode)
{
while(1)
{
if(rootnode.data<value1 && rootnode.vdaata<value2)
rootnode=rootnode.right;
else if(rootnode.data<value1 && rootnode.vdaata<value2)
rootnode=rootnode.left;
}}
return rootnode;

10 and 17 are children of 10 and 40 and 60 are children of 50 :-)

Is this a BST? the position of 15 seems to be wrong. If it's not a BST, we can pick a node as root, then use BFS to traversal

1. Calculate depth of both nodes(lets say A and B) from root node.
2. Start with node having lowest depth(lets say B) among those two.

while (B->parent!=root)
{
       while(A->Parent!=NULL)
         {
            if( B-->Parent == A-->Parent)
                        {
                                    if(B->Parent->Parent == A->Parent->Parent)
                                               LCP = B->Parent;
                                               exit();
                         }
                  A=A->Parent;
                  }
   A= Initial value of A. 
   B=B->Parent;
}

use Tarjan or RMQ algorithm to get better performance

// This code will have the following complexities...

// O(log n) time complexity for finding a particular element.
// O(log n) time complexity for checking if an element exists.
// O(1) constant space complexity since we are not using any extra space or buffer.

// Assumptions:
// A binary search tree is given along with 2 elements. (tree need not be a complete BST)

// We need to find a node which is the lowest common ancestor of the given 2 elements.

// Definition of a node.
struct node
{
	int data;
	struct node *left, *right;
};

// Define a method which finds out if an element exists in the tree. O(log n) operations...
int exists(struct node *rt, int x)
{
	struct node *p=rt;

	while(p!=NULL)
	{
		if(p->data == x)
			return 1;

		if(x<=p->data)
			p=p->left;
		else
			p=p->right;
	}

	// If execution reaches this point, it means element was not found.
	return 0;
}

// Find the LCA... O(log n) operations.
// Returns a pointer to the least common ancestor.
struct node * find_LCA(struct node *rt, int x, int y)
{
	struct node *p=rt;

	while(p!=NULL)
	{
		if(x<=p->data && y<=p->data)
		{
			// Move left.
			p=p->left;
		}
		else if(x>p->data && y>p->data)
		{
			// Move right.
			p=p->right;
		}
		else
		{
			/* Means that we have reached the lowest point in the tree such that the value
			   in node p will have a value greater than one element but lesser that the other.
			   So, all we need to do now is to confirm if those 2 elements actually exist in the tree
			   considering p as the root. If they do, we have found our least common ancestor (which is p)
			
			if(exists(p,x) && exists(p,y))
				return p;
		}
	}

	// If execution reaches this point, it means the LCA was not found. Return NULL.
	return NULL;
}

tree* LCA(tree *root, int lvalue, int rvalue, int index)
{
static int lcaindex = 0;
static tree* lcaroot = root;

if(root == NULL)
return NULL;
else if((findnode(root->left,lvalue) && findnode(root->right, rvalue)) || (findnode(root->left,rvalue) && findnode(root->right, lvalue))
{
if(index > lcaindex)
{
lcaindex = index;
lcaroot = root;
}

}
else
{
LCA(root->left,lvalue,rvalue,index++);
LCA(root->right,lvalue,rvalue,index++);
}

return lcaroot;
}