Table of contents

Introduction

Problem Statement

2.1.

Sample Examples

Algorithm

3.1.

Implementation in C++

3.1.1.

Complexity Analysis

Frequently Asked Questions

4.1.

What is tree data structure?

4.2.

What are the various types of Trees?

4.3.

What are the advantages of using a Tree data structure?

Conclusion

Last Updated: Mar 27, 2024

Medium

Floor and Ceil in a Binary Search Tree

Author Rupal Saluja

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

In this blog, we will understand a very interesting problem based on Binary Search Tree data structure. The problem aims to find the floor and ceil in a Binary Search Tree. There are several applications in which floor or ceil value is needed compulsorily.

For example, in designing a memory management system. In this, all free nodes are arranged in Binary Search Tree. With its help, we can extract memory locations anytime they are needed.

Through this problem, we will learn the approach to finding floor and ceil in a Binary Search Tree. Firstly, we will examine the problem statement, learn about the Binary Search tree data structure, and decide on what will be the optimum approach. Then we will proceed toward the implementation in the programming languages.

What is a Binary Search Tree?

A Binary Search Tree is a type of Binary tree data structure. A Binary Tree is one in which elements have the utmost two child nodes. Since elements in this data structure have only two child nodes, we name them the left child and the right child. Any node of Binary contains the following information. These are its data and pointers to its left and right child.

For Example, if we consider the tree below, 12 is the root node, and the rest of the nodes are its children nodes. We pick any node, say 6, so 4 will be its left child, and 9 will be its right child. 6 is the parent node to children nodes 4 and 9.

Three properties of a Binary Search Tree that differentiate it from a normal Binary Tree. These properties are mentioned below in the list.

The left subtree of any node will contain only those whose value is lesser than that node’s value.
The right subtree of any node will contain only nodes whose value is greater than that node’s value.
All the subtrees must also be binary search trees.

Problem Statement

We are given a binary search tree that has n nodes and a node value. We must find the floor and ceil in a binary tree for the given node.

When we say floor for any node, it means that the node with the largest value, less than or equal to that node. On the other hand, the ceil, for any node, is the node with the smallest value, greater than or equal to that node.

Here, we assume that all the nodes’ values are positive.
Let us understand this with the help of some examples.

Sample Examples

Suppose that we have a binary search tree, as seen in the image below. We have to search for floor and ceil in the given Binary Search Tree. We will use the same binary search tree for different examples to grab all the possible cases better. We will also understand the approach to the solution through these examples.

❄️ Example 1: When both ceil and floor are present in the binary search tree.

Input

n: 23

Output

Floor: 22

Ceil: 35

Explanation

In the above example, we can see a binary search tree.

Firstly, we will find the ceil value by following the steps below. We will create a variable ceil and assign ‘-1’ to it. Then,

Compare the input value ‘n’ with the root value. It did not match. We see that the root value is greater than the input value. So, we will assign the root value to the variable ceil.
Move to its left subtree to check whether any node exists whose value is less than 35 but greater than 23.
We get 17, which is less than the input value. Thus, the value of variable ceil remains 35.
Move to its right subtree. We got 20, which is less than the input value, so the value of variable ceil remains 35.
Shift to its right side. We again got a value that is less than the input value, that is, 22. Thus, the output for ceil variable remains 35.

Now, we will find the floor value by following the below steps. We will follow a similar process as we did for the ceil value. We will create a variable floor and assign ‘-1’ to it. Then,

Start with comparing the input value ‘n’ with the root value of the complete tree. It did not match. We see that the root value is greater than the input value. So. the value of variable floor remains -1.
Move to the left subtree. We got 17, which is less than the input value. Thus, the value of the variable floor changes to 17.
Move to its right subtree to check whether any node exists whose value is greater than 17 but less than 23.
We got 20 which is greater than 17 but less than 23. Now, the value of the variable floor becomes 20.
Again, move to its right subtree. We got 22, which we see is less than 23 and the greatest. Hence, the output for the floor variable is 22.

❄️ Example 2: When floor value is not present.

Input

n: 9

Output

Floor: -1

Ceil: 10

Explanation

Firstly, we will find the ceil value by looking at the steps. We will create a variable ceil and assign ‘-1’ to it.

Compare the input value ‘n’ with the root value. It did not match. We see that the root value is greater than the input value. So, we will assign the root value to the variable ceil, ceil=35.
Move to its left subtree to check whether any node exists whose value is less than 35 but greater than 9.
We get 17, which is greater than the input value but less than 35. Thus, the value of variable ceil changes to 17.
Move to its left subtree. We got 15, which is greater than the input value but less than 17. So, the value of variable ceil changes to 15.
Shift to its left side. We again got a value greater than the input value but less than 15, that is, 10. Thus, the output for ceil variable changes to 10.

Now, we will find the floor value by following the below steps. We will follow a similar process as we did for the ceil value. We will create a variable floor and assign ‘-1’ to it.

Start with comparing the input value ‘n’ with the root value of the complete tree. It did not match. We see that the root value is greater than the input value. So, the value of variable floor remains -1.
Move to the left subtree. We got 17, which is greater than the input value. Thus, the value of the variable floor remains -1.
Move to its left subtree. We got 15, which is greater than the input value. So, the value of the variable floor remains -1.
Again, move to its left subtree. We got 10, which we see is greater than the input value. Hence, the output for the floor variable remains -1.

❄️ Example 3: When ceil value is not present.

Input

n: 55

Output

Floor: 52

Ceil: -1

Explanation

We will find the ceil value by following the below steps. We will create a variable ceil and assign ‘-1’ to it.

Start with comparing the input value ‘n’ with the root value of the complete tree. It did not match. We see that the root value is less than the input value. So. the value of variable floor remains -1.
Move to its right subtree to check whether any node exists whose value is greater than 55.
We got 43, which is less than the input value. Thus, the value of the variable floor remains -1.
Move to its right subtree. We got 52, which is less than the input value. So, the value of the variable floor remains -1.
Note that node with value has got no right child. It is implied that there is no value greater than 52 present in the tree. Hence, the value of ceil variable remains -1.

Now, we will find the floor value by looking at the below steps. We will follow a similar process as we did for the ceil value. We will create a variable floor and assign ‘-1’ to it.

Start with comparing the input value ‘n’ with the root value of the complete tree. It did not match. We see that the root value is less than the input value. So. the value of the variable floor changes to 35.
Move to its right subtree to check whether any node exists whose value is greater than 35 but less than 55.
We got 43, which is less than the input value and less than 55. Thus, the value of the variable floor changes to 43.
Again, move to its right subtree. We got 52, which is greater than 43 but less than 55. Thus, the value of the floor variable changes to 52.
Note that there are no more values present in the tree that are greater than 52. Thus, the value of the floor variable remains 52.

As we are familiar with the problem now, let’s understand the implementation.

Algorithm

Assume that we are moving down the tree as per the problem’s requirements.

Compare the input value with the tree's root value depending on whether we want to find the floor or ceil in a Binary Search Tree.
If the root value matches, the problem is considered solved. if the input value does not match the root value, we will proceed toward the subtrees. By looking at the examples, you must have understood how this problem is being approached.
If the root value is less than the input value, the ceil value cannot be in the left subtree. The floor value may be in the right subtree in such a situation.
If the root value exceeds the input value, the floor value cannot be present in the right subtree. Then, in that situation, the ceil value may be in the left subtree.

Implementation in C++

🍁 Value for the variable ceil.

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

class tree { 
public: 
    int n; 
    tree* l; 
    tree* r; 
};
tree* newNode(int n) 
{ 
    tree* TreeNode = new tree(); 
    TreeNode->n = n; 
    TreeNode->l = NULL; 
    TreeNode->r = NULL; 
    return (TreeNode); 
} 
int Ceil(tree* parent, int input) 
{
    if (parent == NULL) 
        return -1; 
 
    if (parent->n == input) 
        return parent->n; 


    if (parent->n < input) 
        return Ceil(parent->r, input); 
 
    int ceil = Ceil(parent->l, input); 
    return (ceil >= input) ? ceil : parent->n; 
} 
  
int main() 
{ 
    int num;
    cout<<"Enter the value for which you want to find ceil"<< endl;
    cin>>num;
    tree* parent = newNode(15); 
    parent->l = newNode(11); 
    parent->r = newNode(19); 
    parent->l->l = newNode(9); 
    parent->l->r = newNode(13); 
    parent->r->l = newNode(17); 
    parent->r->r = newNode(21); 
    cout << Ceil(parent, num) << endl; 
  
    return 0; 
}

Input:

Output:

-1

🍁 Value for the variable floor.

#include <bits/stdc++.h>
using namespace std;
class tree
{
public:
    int n;
    tree *l;
    tree *r;
};

tree *TreeNode(int n)
{
    tree *node = new tree();
    node->n = n;
    node->l = NULL;
    node->r = NULL;
    return (node);
}
int Floor(tree *parent, int input)
{
    if (parent == NULL)
        return -1;
 
    if (parent->n == input)
        return parent->n;
 
    if (parent->n > input)
        return Floor(parent->l, input);

    else{
        int floor = Floor(parent->r, input);
        return (floor<=input && floor!=-1)? floor : parent->n; 
    }
} 

int main()
{
    int num;
    cout<< "Enter the number for which you have to find the floor" << endl;
    cin>> num;
    tree *parent = TreeNode(16);
    parent->l = TreeNode(12);
    parent->r = TreeNode(20);
    parent->l->l = TreeNode(10);
    parent->l->r = TreeNode(14);
    parent->r->l = TreeNode(18);
    parent->r->r = TreeNode(22);
    cout << Floor(parent, num) << endl;
  
    return 0;
}

Input:

Output:

Complexity Analysis

🥝 Time Complexity: O(log n)

In the implementation above, the tree gets divided into two every time we decide which subtree we should move ahead with. Therefore, in this case, the time complexity will be O(log n).

🥝 Space Complexity: O(log n)

A recursive call which is allowing the elements to push and pop from the stack has been made. The number of recursive calls increases logarithmically, that is, ‘n’ is halved with every recursive call. Therefore, the space complexity, in this case, will be O(log n).

Check out this problem - Diameter Of Binary Tree

Frequently Asked Questions

What is tree data structure?

A hierarchical data structure that does not sequentially store values is known as a Tree data structure. It is a non-linear data structure, and values are arranged on multiple levels. The topmost node is known as the root node or parent node. The nodes at the bottom are known as child nodes or leaf nodes.

What are the various types of Trees?

The various types of trees that are present in the tree data structure are:

General Tree

Binary Tree

Binary Search Tree

AVL Tree

Red Black Tree

N-ary Tree

What are the advantages of using a Tree data structure?

A few advantages of using Tree data structure are:

Hierarchical way of storing data

Presents structural relationship

Most Flexible way to hold and move data

Allows all the basic operations of data structure

Conclusion

To summarize the article, we looked at the problem statement, looked at every possible condition that could occur, understood the approach, went through the Algorithm, saw the implementation, tested the code against an example input, and did the time and space complexities’ analysis.

We hope the above discussion helped you understand and solve the problem better.

This will also help you learn how to approach any problem like this in the future.

For coders who want to solve more such questions, refer to the list below.

Enroll in our courses, go for mock tests, solve problems available, and interview puzzles. Also, you can focus on interview stuff- interview experiences and an interview bundle for placement preparations. Do upvote our blog to help other ninjas grow.

Happy Coding!