Given a \(\texttt{BST}\) containing $n$ nodes, write a function that runs in \(\mathcal{O}(\log{}n)\) that finds the \(\texttt{floor}\) and the \(\texttt{ceil}\) of a value \(\texttt{val}\) given as parameter.
If \(\texttt{val}\) exists in the tree, its \(\texttt{floor}\) and \(\texttt{ceil}\) is \(\texttt{val}\) itself. 
If not, the \(\texttt{floor}\) of \(\texttt{val}\) is the previous value that comes directly before \(\texttt{val}\) in the tree and the \(\texttt{ceil}\) is the next value that comes directly after \(\texttt{val}\) in the tree. 

Here are some examples.

     8
   /    \
  4     10
 / \    / \
2 6   9 12

 

\(\texttt{floor}\) of 1 do no exist, \(\texttt{ceil}\) of 1 is 2
\(\texttt{floor}\) of 3 is 2, \(\texttt{ceil}\) of 3 is 4
\(\texttt{floor}\) of 9 is 9, \(\texttt{ceil}\) of 9 is 9
\(\texttt{floor}\) of 7 is 6, \(\texttt{ceil}\) of 7 is 8


Difficulty level
This exercise is mostly suitable for students
Recursive version
void find(BST B, int v, int *floor, int *ceil)
{
	if (B)
	{
		if (B->data == v)
			*floor = *ceil = B->data;
		else
			if (B->data < v)
			{
				*floor = B->data;
				find(B->right, v, floor, ceil);
			}
			else
				if (B->data > v)
				{
					*ceil = B->data;
					find(B->left, v, floor, ceil);
				}
	}
} 

Iterative version
void find(BST B, int v, int *floor, int *ceil)
{
	while (B)
	{
		if (B->data == v)
		{
			*floor = *ceil = B->data;
			break;
		}
		else
			if (B->data < v)
			{
				*floor = B->data;
				B=B->right;
			}
			else
				if (B->data > v)
				{
					*ceil = B->data;
					B=B->left;
				}
	}
} 

Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Left rotate an array