Floor and Ceil in a Binary Search Tree

By | February 29, 2016

Floor and Ceil in a Binary Search Tree

Problem statement to find Floor and Ceil in a Binary Search Tree (BST).

In mathematics and computer science, the floor and ceiling functions map a real number to the largest previous or the smallest following integer, respectively. More precisely, floor(x) = is the largest integer not greater than x and ceiling(x) = is the smallest integer not less than x.

Given a binary search tree (BST), we need to determine floor and ceil value of a key.

Example for finding Floor and Ceil in a Binary Search Tree (BST):

Input: 
                7
             /     \
            5        10
          /   \     /   \
         3     6   8     12
Output:
Ceil of 9 is 10
floor of 9 is 8

Solution to determine floor and ceil of a key in a binary search tree:

According to binary search tree (BST) property, elements of left subtree must be smaller than the root and elements of right subtree must be greater than the root.

If the key is less than the value at the root of a BST then floor of key must be in the left subtree. If key is greater than the key at the root then floor of key could be in the right subtree, but only if there is a key smaller than or equal to key in the right subtree; If not then the key at the root is floor of the key.

Similarly for ceil, If the key is greater than the value at the root of a BST then ceil of key must be in the right subtree. If key is less than the key at the root then floor of key could be in the left subtree, but only if there is a value greater than or equal to key in the left subtree; If not then the key at the root is ceil of the key.


TO FIND CEIL OF A KEY:

Algorithm to find the ceil of a key in a binary search tree (BST):

  1. Start at the root node.
  2. If root->data == key , then ceil of the key is equal to the root.
  3. Else if root->data < key, then ceil of the key must lie in the right subtree.
  4. Else ceil may lie in the left subtree but only if there is a value greater than or equal to the key.If not, then root is the key.

Solution code in C++ to find Ceil in a Binary Search Tree(BST):

#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
   int data;
   node *left;
   node *right;
};

/*This function is used to create and
initialises new nodes*/
node *newNode(int key)
{
   node *temp=new node;
   temp->left=NULL;
   temp->right=NULL;
   temp->data=key;
   return temp;
}

/*This funciton is used to Insert
 new values in BST*/
node *Insert(node *root,int key)
{
   if(!root)
      return newNode(key);
   if(key<root->data)	
      root->left=Insert(root->left,key);
   else
      root->right=Insert(root->right,key);
   return root;
}

/*This function is used to find ceil of a key*/
int ceil(node *root, int key)
{
   if(!root)
      return -1;
   
   /*If root->data is equal to key*/
   if(root->data == key)
   		return root->data;
   		
   /*If root->data is less than the key*/
   if(root->data < key)
   		return ceil(root->right, key);
   		
   /*Else, the ceil may lie in left subtree
   or may be equal to the root*/ 
   int ceilValue = ceil(root->left, key);
   return (ceilValue >= key) ? ceilValue : root->data;
}

int main() {
   /* Let us create following BST
              7
            /    \
           5      10
         /  \    /  \
        3    6   8   12 */
    node *root = NULL;
    root = Insert(root, 7);
    Insert(root, 10);
    Insert(root, 5);
    Insert(root, 3);
    Insert(root, 6);
    Insert(root, 8);
    Insert(root, 12);
 
 	for(int i=0; i<16; i++)
 	{
 		cout<<i<<" -> "<<ceil(root,i)<<endl;
 	}
   return 0;
}

OUTPUT:

0 -> 3
1 -> 3
2 -> 3
3 -> 3
4 -> 5
5 -> 5
6 -> 6
7 -> 7
8 -> 8
9 -> 10
10 -> 10
11 -> 12
12 -> 12
13 -> -1
14 -> -1
15 -> -1

 Time Complexity:O(n)


TO FIND FLOOR OF A KEY:

Algorithm to find the floor of a key in a binary search tree (BST):

  1. Start at the root node.
  2. If root->data == key , then floor of the key is equal to the root.
  3. Else if root->data > key, then ceil of the key must lie in the left subtree.
  4. Else floor may lie in the right subtree but only if there is a value lesser than or equal to the key.If not, then root is the key.

Solution code in C++ to find Floor in a Binary Search Tree(BST):

#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
   int data;
   node *left;
   node *right;
};

/*This function is used to create and
initialises new nodes*/
node *newNode(int key)
{
   node *temp=new node;
   temp->left=NULL;
   temp->right=NULL;
   temp->data=key;
   return temp;
}

/*This funciton is used to Insert
 new values in BST*/
node *Insert(node *root,int key)
{
   if(!root)
      return newNode(key);
   if(key<root->data)	
      root->left=Insert(root->left,key);
   else
      root->right=Insert(root->right,key);
   return root;
}

/*This function is used to
print Inorder traversal*/
void Inorder(node *root)
{
   if(!root)
      return;
   Inorder(root->left);
   cout<<root->data<<" ";
   Inorder(root->right);
}

/*This function is used to find floor of a key*/
int floor(node *root, int key)
{
   if(!root)
      return INT_MAX;
   
   /*If root->data is equal to key*/
   if(root->data == key)
   		return root->data;
   		
   /*If root->data is greater than the key*/
   if(root->data > key)
   		return floor(root->left, key);
   		
   /*Else, the floor may lie in right subtree
   or may be equal to the root*/ 
   int floorValue = floor(root->right, key);
   return (floorValue <= key) ? floorValue : root->data;
}

int main() {
   /* Let us create following BST
              7
            /    \
           5      10
         /  \    /  \
        3    6   8   12 */
    node *root = NULL;
    root = Insert(root, 7);
    Insert(root, 10);
    Insert(root, 5);
    Insert(root, 3);
    Insert(root, 6);
    Insert(root, 8);
    Insert(root, 12);
 
 	for(int i=3; i<16; i++)
 	{
 		cout<<i<<" -> "<<floor(root,i)<<endl;
 	}
   return 0;
}

OUTPUT:

3 -> 3
4 -> 3
5 -> 5
6 -> 6
7 -> 7
8 -> 8
9 -> 8
10 -> 10
11 -> 10
12 -> 12
13 -> 12
14 -> 12
15 -> 12

Time Complexity:O(n)