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.
Input Binary Search Tree: 
❄️ 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.