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

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.

Below is C++ implementation of the idea:

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#include <iostream> #include <iomanip> using namespace std; // Data structure to store a Binary Search Tree node struct Node { int data; Node *left, *right; }; // Function to create a new binary tree node having given key Node* newNode(int key) { Node* node = new Node; node->data = key; node->left = node->right = nullptr; return node; } // Recursive function to insert an key into BST Node* insert(Node* root, int key) { // if the root is null, create a new node an return it if (root == nullptr) return newNode(key); // if given key is less than the root node, recurse for left subtree if (key < root->data) root->left = insert(root->left, key); // if given key is more than the root node, recurse for right subtree else root->right = insert(root->right, key); return root; } // Recursive function to find floor and ceil of a given key in a BST // Note that floor and ceil is passed by reference to the function void findFloorCeil(Node* root, Node* &floor, Node* &ceil, int key) { // base case if(root == nullptr) return; // if node with key's value is found, both floor and ceil is equal // to the current node if (root->data == key) { floor = root; ceil = root; } // if given key is less than the root node, recurse for left subtree else if (key < root->data) { // update ceil to current node before recursing in left subtree ceil = root; findFloorCeil(root->left, floor, ceil, key); } // if given key is more than the root node, recurse for right subtree else { // update floor to current node before recursing in right subtree floor = root; findFloorCeil(root->right, floor, ceil, key); } } // main function int main() { /* Construct below tree 8 / \ / \ 4 10 / \ / \ / \ / \ 2 6 9 12 */ int keys[] = { 2, 4, 6, 8, 9, 10, 12 }; Node* root = nullptr; for (int key : keys) root = insert(root, key); // find Ceil and Floor for each key for (int i = 0; i < 15; i++) { Node *floor = nullptr, *ceil = nullptr; findFloorCeil(root, floor, ceil, i); cout << setw(2) << i << " --> "; cout << setw(4) << (floor? floor->data: -1); cout << setw(4) << (ceil? ceil->data: -1) << endl; } return 0; } |

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.

Below is C++ implementation of the idea:

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// Recursive function to find floor and ceil of a given key in a BST // Note that floor and ceil is passed by reference to the function void findFloorCeil(Node* root, Node* &floor, Node* &ceil, int key) { while (root) { // if node with key's value is found, both floor and ceil is equal // to the current node if (root->data == key) { floor = root; ceil = root; break; } // if given key is less than the root node, visit left subtree else if (key < root->data) { // update ceil to current node before visiting left subtree ceil = root; root = root->left; } // if given key is more than the root node, visit right subtree else { // update floor to current node before visiting right subtree floor = root; root = root->right; } } } |

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

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply