# Floor and Ceil from a BST

There are numerous applications we need to find floor (ceil) value of a key in a binary search tree or sorted array. For example, consider designing memory management system in which free nodes are arranged in BST. Find best fit for the input request.

Ceil Value Node: Node with smallest data larger than or equal to key value.

Imagine we are moving down the tree, and assume we are root node. The comparison yields three possibilities,

A) Root data is equal to key. We are done, root data is ceil value.

B) Root data < key value, certainly the ceil value can’t be in left subtree. Proceed to search on right subtree as reduced problem instance.

C) Root data > key value, the ceil value may be in left subtree. We may find a node with is larger data than key value in left subtree, if not the root itself will be ceil node.

Here is the code for ceil value.

div class="responsive-tabs">

## C++

 `// Program to find ceil of a given value in BST ` `#include ` `using` `namespace` `std; ` ` `  `/* A binary tree node has key, left child and right child */` `class` `node { ` `public``: ` `    ``int` `key; ` `    ``node* left; ` `    ``node* right; ` `}; ` ` `  `/* Helper function that allocates a new node with the given key and  ` `NULL left and right pointers.*/` `node* newNode(``int` `key) ` `{ ` `    ``node* Node = ``new` `node(); ` `    ``Node->key = key; ` `    ``Node->left = NULL; ` `    ``Node->right = NULL; ` `    ``return` `(Node); ` `} ` ` `  `// Function to find ceil of a given input in BST. If input is more ` `// than the max key in BST, return -1 ` `int` `Ceil(node* root, ``int` `input) ` `{ ` `    ``// Base case ` `    ``if` `(root == NULL) ` `        ``return` `-1; ` ` `  `    ``// We found equal key ` `    ``if` `(root->key == input) ` `        ``return` `root->key; ` ` `  `    ``// If root's key is smaller, ceil must be in right subtree ` `    ``if` `(root->key < input) ` `        ``return` `Ceil(root->right, input); ` ` `  `    ``// Else, either left subtree or root has the ceil value ` `    ``int` `ceil` `= Ceil(root->left, input); ` `    ``return` `(``ceil` `>= input) ? ``ceil` `: root->key; ` `} ` ` `  `// Driver program to test above function ` `int` `main() ` `{ ` `    ``node* root = newNode(8); ` ` `  `    ``root->left = newNode(4); ` `    ``root->right = newNode(12); ` ` `  `    ``root->left->left = newNode(2); ` `    ``root->left->right = newNode(6); ` ` `  `    ``root->right->left = newNode(10); ` `    ``root->right->right = newNode(14); ` ` `  `    ``for` `(``int` `i = 0; i < 16; i++) ` `        ``cout << i << ``" "` `<< Ceil(root, i) << endl; ` ` `  `    ``return` `0; ` `} ` ` `  `// This code is contributed by rathbhupendra `

## C

 `// Program to find ceil of a given value in BST ` `#include ` `#include ` ` `  `/* A binary tree node has key, left child and right child */` `struct` `node { ` `    ``int` `key; ` `    ``struct` `node* left; ` `    ``struct` `node* right; ` `}; ` ` `  `/* Helper function that allocates a new node with the given key and ` `NULL left and right pointers.*/` `struct` `node* newNode(``int` `key) ` `{ ` `    ``struct` `node* node = (``struct` `node*)``malloc``(``sizeof``(``struct` `node)); ` `    ``node->key = key; ` `    ``node->left = NULL; ` `    ``node->right = NULL; ` `    ``return` `(node); ` `} ` ` `  `// Function to find ceil of a given input in BST. If input is more ` `// than the max key in BST, return -1 ` `int` `Ceil(``struct` `node* root, ``int` `input) ` `{ ` `    ``// Base case ` `    ``if` `(root == NULL) ` `        ``return` `-1; ` ` `  `    ``// We found equal key ` `    ``if` `(root->key == input) ` `        ``return` `root->key; ` ` `  `    ``// If root's key is smaller, ceil must be in right subtree ` `    ``if` `(root->key < input) ` `        ``return` `Ceil(root->right, input); ` ` `  `    ``// Else, either left subtree or root has the ceil value ` `    ``int` `ceil` `= Ceil(root->left, input); ` `    ``return` `(``ceil` `>= input) ? ``ceil` `: root->key; ` `} ` ` `  `// Driver program to test above function ` `int` `main() ` `{ ` `    ``struct` `node* root = newNode(8); ` ` `  `    ``root->left = newNode(4); ` `    ``root->right = newNode(12); ` ` `  `    ``root->left->left = newNode(2); ` `    ``root->left->right = newNode(6); ` ` `  `    ``root->right->left = newNode(10); ` `    ``root->right->right = newNode(14); ` ` `  `    ``for` `(``int` `i = 0; i < 16; i++) ` `        ``printf``(````"%d %d "````, i, Ceil(root, i)); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to find ceil of a given value in BST  ` ` `  `class` `Node {  ` ` `  `    ``int` `data;  ` `    ``Node left, right;  ` ` `  `    ``Node(``int` `d)  ` `    ``{  ` `        ``data = d;  ` `        ``left = right = ``null``;  ` `    ``}  ` `}  ` ` `  `class` `BinaryTree {  ` ` `  `    ``Node root;  ` ` `  `    ``// Function to find ceil of a given input in BST.  ` `    ``// If input is more than the max key in BST,  ` `    ``// return -1  ` `    ``int` `Ceil(Node node, ``int` `input)  ` `    ``{  ` ` `  `        ``// Base case  ` `        ``if` `(node == ``null``) {  ` `            ``return` `-``1``;  ` `        ``}  ` ` `  `        ``// We found equal key  ` `        ``if` `(node.data == input) {  ` `            ``return` `node.data;  ` `        ``}  ` ` `  `        ``// If root's key is smaller,  ` `        ``// ceil must be in right subtree  ` `        ``if` `(node.data < input) {  ` `            ``return` `Ceil(node.right, input);  ` `        ``}  ` ` `  `        ``// Else, either left subtree or root ` `        ``// has the ceil value  ` `        ``int` `ceil = Ceil(node.left, input);  ` `         `  `        ``return` `(ceil >= input) ? ceil : node.data;  ` `    ``}  ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{  ` `        ``BinaryTree tree = ``new` `BinaryTree();  ` `        ``tree.root = ``new` `Node(``8``);  ` `        ``tree.root.left = ``new` `Node(``4``);  ` `        ``tree.root.right = ``new` `Node(``12``);  ` `        ``tree.root.left.left = ``new` `Node(``2``);  ` `        ``tree.root.left.right = ``new` `Node(``6``);  ` `        ``tree.root.right.left = ``new` `Node(``10``);  ` `        ``tree.root.right.right = ``new` `Node(``14``);  ` `        ``for` `(``int` `i = ``0``; i < ``16``; i++) {  ` `             `  `            ``System.out.println(i + ``" "` `+  ` `                        ``tree.Ceil(tree.root, i));  ` `        ``}  ` `    ``}  ` `}  ` ` `  `// This code has been contributed by Mayank Jaiswal  `

## Python

 `# Python program to find ceil of a given value in BST ` ` `  `# A Binary tree node ` `class` `Node: ` `     `  `    ``# Constructor to create a new node ` `    ``def` `__init__(``self``, data): ` `        ``self``.key ``=` `data ` `        ``self``.left ``=` `None` `        ``self``.right ``=` `None` ` `  `# Function to find ceil of a given input in BST. If input ` `# is more than the max key in BST, return -1 ` `def` `ceil(root, inp): ` `     `  `    ``# Base Case ` `    ``if` `root ``=``=` `None``: ` `        ``return` `-``1` `     `  `    ``# We found equal key ` `    ``if` `root.key ``=``=` `inp : ` `        ``return` `root.key  ` `     `  `    ``# If root's key is smaller, ceil must be in right subtree ` `    ``if` `root.key < inp: ` `        ``return` `ceil(root.right, inp) ` `     `  `    ``# Else, either left subtre or root has the ceil value ` `    ``val ``=` `ceil(root.left, inp) ` `    ``return` `val ``if` `val >``=` `inp ``else` `root.key  ` ` `  `# Driver program to test above function ` `root ``=` `Node(``8``) ` ` `  `root.left ``=` `Node(``4``) ` `root.right ``=` `Node(``12``) ` ` `  `root.left.left ``=` `Node(``2``) ` `root.left.right ``=` `Node(``6``) ` ` `  `root.right.left ``=` `Node(``10``) ` `root.right.right ``=` `Node(``14``) ` ` `  `for` `i ``in` `range``(``16``): ` `    ``print` `"% d % d"` `%``(i, ceil(root, i)) ` ` `  `# This code is contributed by Nikhil Kumar Singh(nickzuck_007) `

## C#

 `using` `System; ` ` `  `// C# program to find ceil of a given value in BST ` ` `  `public` `class` `Node { ` ` `  `    ``public` `int` `data; ` `    ``public` `Node left, right; ` ` `  `    ``public` `Node(``int` `d) ` `    ``{ ` `        ``data = d; ` `        ``left = right = ``null``; ` `    ``} ` `} ` ` `  `public` `class` `BinaryTree { ` ` `  `    ``public` `static` `Node root; ` ` `  `    ``// Function to find ceil of a given input in BST. If input is more ` `    ``// than the max key in BST, return -1 ` `    ``public` `virtual` `int` `Ceil(Node node, ``int` `input) ` `    ``{ ` ` `  `        ``// Base case ` `        ``if` `(node == ``null``) { ` `            ``return` `-1; ` `        ``} ` ` `  `        ``// We found equal key ` `        ``if` `(node.data == input) { ` `            ``return` `node.data; ` `        ``} ` ` `  `        ``// If root's key is smaller, ceil must be in right subtree ` `        ``if` `(node.data < input) { ` `            ``return` `Ceil(node.right, input); ` `        ``} ` ` `  `        ``// Else, either left subtree or root has the ceil value ` `        ``int` `ceil = Ceil(node.left, input); ` `        ``return` `(ceil >= input) ? ceil : node.data; ` `    ``} ` ` `  `    ``// Driver program to test the above functions ` `    ``public` `static` `void` `Main(``string``[] args) ` `    ``{ ` `        ``BinaryTree tree = ``new` `BinaryTree(); ` `        ``BinaryTree.root = ``new` `Node(8); ` `        ``BinaryTree.root.left = ``new` `Node(4); ` `        ``BinaryTree.root.right = ``new` `Node(12); ` `        ``BinaryTree.root.left.left = ``new` `Node(2); ` `        ``BinaryTree.root.left.right = ``new` `Node(6); ` `        ``BinaryTree.root.right.left = ``new` `Node(10); ` `        ``BinaryTree.root.right.right = ``new` `Node(14); ` `        ``for` `(``int` `i = 0; i < 16; i++) { ` `            ``Console.WriteLine(i + ``" "` `+ tree.Ceil(root, i)); ` `        ``} ` `    ``} ` `} ` ` `  `// This code is contributed by Shrikant13 `

Output:

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

Exercise:

1. Modify above code to find floor value of input key in a binary search tree.

2. Write neat algorithm to find floor and ceil values in a sorted array. Ensure to handle all possible boundary conditions.

## tags:

Binary Search Tree Binary Search Tree