Floor and Ceil in a Binary Search Tree

Given a BST, find ceil and floor 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


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

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.

 
C++ implementation –
 

Download   Run Code

 
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.

 
C++ implementation –
 

Download   Run Complete Code

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

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂