# Floor and Ceil in a Binary Search Tree

Given a BST, find floor and ceil of a given key in it. If the given key lie in the BST, then both floor and ceil is equal to that key, else ceil is equal to next greater key (if any) in the BST and floor is equal to previous greater key (if any) in the BST.

For example, consider below tree

floor of 1 do not exist, ceil of 1 is 2
floor of 3 is 2, ceil of 3 is 4
floor of 9 is 9, ceil of 9 is 9
floor of 7 is 6, ceil of 7 is 8

The idea is very simple. We recursively search for given key in the tree and update the ceil to current node before visiting its left subtree and update the floor to current node before visiting its right subtree. If the key is found in the BST, then floor and ceil is equal to that key. If the key is not found in the BST, then floor and ceil were already updated while searching for the key.

Below is C++ implementation of the idea:

## C++

The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.

#### Iterative version –

The same algorithm can be easily implemented iteratively.

Below is C++ implementation of the idea:

## C++

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

(1 votes, average: 5.00 out of 5)