Antoun J. Yaacoub Ph.D.

Given pointers to two nodes in a BST dynamically implemented, write a function that returns a pointer to their lowest common ancestor.
Restrictions:

Time complexity of your function: $O(\log{n})$, where $n$ is the number of nodes.
Usage of stacks and queues is not allowed.

Difficulty level

This exercise is mostly suitable for students

typedef int element;

typedef struct node
{
	element data;
	struct node *left,*right;
} *BST;

Iterative version
BST lca(BST root, BST A, BST B)
{
	while (1)
	{
		if (A->data < root->data && B->data > root->data ||
			A->data > root->data && B->data< root->data)
			return root;
		if (A->data < root->data)
			root = root->left;
		else
			root = root->right;
	}
}

Recursive version
BST lcarec(BST root, BST A, BST B)
{
		if (A->data < root->data && B->data > root->data ||
			A->data > root->data && B->data< root->data)
			return root;
		if (A->data < root->data)
			return lcarec(root->left, A, B);
		return lcarec(root->right, A, B);
}

Back to the list of exercises

Looking for a more challenging exercise, try this one !!

Sum a range of integers using recursion

Lowest common ancestor in a BST