Find Floor and Ceil in a Binary Search Tree
Given a BST, find the floor and ceil of a given key in it. If the given key lies in the BST, then both floor and ceil are equal to that key; otherwise, the ceil is equal to the next greater key (if any) in the BST, and the floor is equal to the previous greater key (if any) in the BST.
For example, consider the following tree:
The floor of 1 does not exist, ceil of 1 is 2
The floor of 3 is 2, ceil of 3 is 4
The floor of 9 is 9, ceil of 9 is 9
The floor of 7 is 6, ceil of 7 is 8
The idea is simple – search for the given key in the tree and update the ceil to the current node before visiting its left subtree. Similarly, update the floor to the current node before visiting its right subtree. If the key is found in the BST, then the floor and ceil are equal to that key. If the key is not found in the BST, then the floor and ceil were already updated while searching for the key.
Following is the iterative implementation of the above approach in C++, Java, and Python:
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 |
#include <iostream> #include <iomanip> using namespace std; // Data structure to store a BST node struct Node { int data; Node* left = nullptr, *right = nullptr; Node() {} Node(int data): data(data) {} }; // Recursive function to insert a key into a BST Node* insert(Node* root, int key) { // if the root is null, create a new node and return it if (root == nullptr) { return new Node(key); } // if the given key is less than the root node, recur for the left subtree if (key < root->data) { root->left = insert(root->left, key); } // if the given key is more than the root node, recur for the right subtree else { root->right = insert(root->right, key); } return root; } // Recursive function to find the floor and ceil of a given key in a BST. // Note that floor and ceil are passed by reference to the function void findFloorCeil(Node* root, Node* &floor, Node* &ceil, int key) { while (root) { // if a node with the desired value is found, both floor and ceil is equal // to the current node if (root->data == key) { floor = root; ceil = root; break; } // if the given key is less than the root node, visit the left subtree else if (key < root->data) { // update ceil to the current node before visiting the left subtree ceil = root; root = root->left; } // if the given key is more than the root node, visit the right subtree else { // update floor to the current node before visiting the right subtree floor = root; root = root->right; } } } int main() { /* Construct the following 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 the 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; } |
Java
|
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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
// A class to store a BST node class Node { int data; Node left, right; Node(int data) { this.data = data; } } class FloorCeil { private Node floor, ceil; FloorCeil() { floor = new Node(-1); ceil = new Node(-1); } public void setCeil(Node ceil) { this.ceil = ceil; } public void setFloor(Node floor) { this.floor = floor; } public int getCeilData() { return ceil.data; } public int getFloorData() { return floor.data; } } class Main { // Recursive function to insert a key into a BST public static Node insert(Node root, int key) { // if the root is null, create a new node and return it if (root == null) { return new Node(key); } // if the given key is less than the root node, recur for the left subtree if (key < root.data) { root.left = insert(root.left, key); } // if the given key is more than the root node, recur for the right subtree else { root.right = insert(root.right, key); } return root; } // Recursive function to find the floor and ceil of a given key in the BST. public static void findFloorCeil(Node root, FloorCeil obj, int key) { while (root != null) { // if a node with the desired value is found, both floor and ceil is equal // to the current node if (root.data == key) { obj.setFloor(root); obj.setCeil(root); break; } // if the given key is less than the root node, visit the left subtree else if (key < root.data) { // update ceil to the current node before visiting the left subtree obj.setCeil(root); root = root.left; } // if the given key is more than the root node, visit the right subtree else { // update floor to the current node before visiting the right subtree obj.setFloor(root); root = root.right; } } } public static void main(String[] args) { /* Construct the following tree 8 / \ / \ 4 10 / \ / \ / \ / \ 2 6 9 12 */ int[] keys = { 2, 4, 6, 8, 9, 10, 12 }; Node root = null; for (int key: keys) { root = insert(root, key); } // find the ceil and floor for each key for (int i = 0; i < 15; i++) { FloorCeil ob = new FloorCeil(); findFloorCeil(root, ob, i); System.out.println(i + " —> Floor is " + ob.getFloorData() + ", Ceil is " + ob.getCeilData()); } } } |
Python
|
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 |
# A class to store a BST node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Recursive function to insert a key into a BST def insert(root, key): # if the root is None, create a new node and return it if root is None: return Node(key) # if the given key is less than the root node, recur for the left subtree if key < root.data: root.left = insert(root.left, key) # if the given key is more than the root node, recur for the right subtree else: root.right = insert(root.right, key) return root # Recursive function to find the floor and ceil of a given key in a BST def findFloorCeil(root, floor, ceil, key): while root: # if a node with the desired value is found, both floor and ceil is equal # to the current node if root.data == key: floor = ceil = root break # if the given key is less than the root node, visit the left subtree elif key < root.data: # update ceil to the current node before visiting the left subtree ceil = root root = root.left # if the given key is more than the root node, visit the right subtree else: # update floor to the current node before visiting the right subtree floor = root root = root.right return floor, ceil if __name__ == '__main__': ''' Construct the following tree 8 / \ / \ 4 10 / \ / \ / \ / \ 2 6 9 12 ''' keys = [2, 4, 6, 8, 9, 10, 12] root = None for key in keys: root = insert(root, key) # find the ceil and floor for each key for i in range(15): floor, ceil = findFloorCeil(root, None, None, i) print(i, end=' —> ') print('Floor is', floor.data if floor else None, end=' and ') print('Ceil is', ceil.data if ceil else None) |
Output:
0 —> Floor is -1, Ceil is 2
1 —> Floor is -1, Ceil is 2
2 —> Floor is 2, Ceil is 2
3 —> Floor is 2, Ceil is 4
4 —> Floor is 4, Ceil is 4
5 —> Floor is 4, Ceil is 6
6 —> Floor is 6, Ceil is 6
7 —> Floor is 6, Ceil is 8
8 —> Floor is 8, Ceil is 8
9 —> Floor is 9, Ceil is 9
10 —> Floor is 10, Ceil is 10
11 —> Floor is 10, Ceil is 12
12 —> Floor is 12, Ceil is 12
13 —> Floor is 12, Ceil is -1
14 —> Floor is 12, Ceil is -1
0 —> Floor is -1, Ceil is 2
1 —> Floor is -1, Ceil is 2
2 —> Floor is 2, Ceil is 2
3 —> Floor is 2, Ceil is 4
4 —> Floor is 4, Ceil is 4
5 —> Floor is 4, Ceil is 6
6 —> Floor is 6, Ceil is 6
7 —> Floor is 6, Ceil is 8
8 —> Floor is 8, Ceil is 8
9 —> Floor is 9, Ceil is 9
10 —> Floor is 10, Ceil is 10
11 —> Floor is 10, Ceil is 12
12 —> Floor is 12, Ceil is 12
13 —> Floor is 12, Ceil is -1
14 —> Floor is 12, Ceil is -1
The time complexity of the above solution is O(n), where n is the size of the BST. The auxiliary space required by the program is O(1).
Following is the recursive C++, Java, and Python 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 |
#include <iostream> #include <iomanip> using namespace std; // Data structure to store a BST node struct Node { int data; Node* left = nullptr, *right = nullptr; Node() {} Node(int data): data(data) {} }; // Recursive function to insert a key into a BST Node* insert(Node* root, int key) { // if the root is null, create a new node and return it if (root == nullptr) { return new Node(key); } // if the given key is less than the root node, recur for the left subtree if (key < root->data) { root->left = insert(root->left, key); } // if the given key is more than the root node, recur for the right subtree else { root->right = insert(root->right, key); } return root; } // Recursive function to find the floor and ceil of a given key in a BST. // Note that floor and ceil are passed by reference to the function void findFloorCeil(Node* root, Node* &floor, Node* &ceil, int key) { // base case if (root == nullptr) { return; } // if a node with the desired value is found, both floor and ceil is equal // to the current node if (root->data == key) { floor = root; ceil = root; } // if the given key is less than the root node, recur for the left subtree else if (key < root->data) { // update ceil to the current node before recursing in the left subtree ceil = root; findFloorCeil(root->left, floor, ceil, key); } // if the given key is more than the root node, recur for the right subtree else { // update floor to the current node before recursing in the right subtree floor = root; findFloorCeil(root->right, floor, ceil, key); } } int main() { /* Construct the following 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); } // calculate the 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; } |
Java
|
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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
// A class to store a BST node class Node { int data; Node left, right; Node(int data) { this.data = data; } } class FloorCeil { private Node floor, ceil; FloorCeil() { floor = new Node(-1); ceil = new Node(-1); } public void setCeil(Node ceil) { this.ceil = ceil; } public void setFloor(Node floor) { this.floor = floor; } public int getCeilData() { return ceil.data; } public int getFloorData() { return floor.data; } } class Main { // Recursive function to insert a key into a BST public static Node insert(Node root, int key) { // if the root is null, create a new node and return it if (root == null) { return new Node(key); } // if the given key is less than the root node, recur for the left subtree if (key < root.data) { root.left = insert(root.left, key); } // if the given key is more than the root node, recur for the right subtree else { root.right = insert(root.right, key); } return root; } // Recursive function to find the floor and ceil of a given key in the BST public static void findFloorCeil(Node root, FloorCeil obj, int key) { // base case if (root == null) { return; } // if a node with the desired value is found, both floor and ceil is equal // to the current node if (root.data == key) { obj.setFloor(root); obj.setCeil(root); } // if the given key is less than the root node, recur for the left subtree else if (key < root.data) { // update ceil to the current node before visiting the left subtree obj.setCeil(root); findFloorCeil(root.left, obj, key); } // if the given key is more than the root node, recur for the right subtree else { // update floor to the current node before visiting the right subtree obj.setFloor(root); findFloorCeil(root.right, obj, key); } } public static void main(String[] args) { /* Construct the following tree 8 / \ / \ 4 10 / \ / \ / \ / \ 2 6 9 12 */ int[] keys = { 2, 4, 6, 8, 9, 10, 12 }; Node root = null; for (int key: keys) { root = insert(root, key); } // calculate the ceil and floor for each key for (int i = 0; i < 15; i++) { FloorCeil ob = new FloorCeil(); findFloorCeil(root, ob, i); System.out.println(i + " —> Floor is " + ob.getFloorData() + ", Ceil is " + ob.getCeilData()); } } } |
Python
|
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 |
# A class to store a BST node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Recursive function to insert a key into a BST def insert(root, key): # if the root is None, create a new node and return it if root is None: return Node(key) # if the given key is less than the root node, recur for the left subtree if key < root.data: root.left = insert(root.left, key) # if the given key is more than the root node, recur for the right subtree else: root.right = insert(root.right, key) return root # Recursive function to find the floor and ceil of a given key in a BST def findFloorCeil(root, floor, ceil, key): # base case if root is None: return floor, ceil # if a node with the desired value is found, both floor and ceil is equal # to the current node if root.data == key: return root, root # if the given key is less than the root node, recur for the left subtree elif key < root.data: # update ceil to the current node before visiting the left subtree return findFloorCeil(root.left, floor, root, key) # if the given key is more than the root node, recur for the right subtree else: # update floor to the current node before visiting the right subtree return findFloorCeil(root.right, root, ceil, key) if __name__ == '__main__': ''' Construct the following tree 8 / \ / \ 4 10 / \ / \ / \ / \ 2 6 9 12 ''' keys = [2, 4, 6, 8, 9, 10, 12] root = None for key in keys: root = insert(root, key) # calculate the ceil and floor for each key for i in range(15): floor, ceil = findFloorCeil(root, None, None, i) print(i, end=' —> ') print('Floor is', floor.data if floor else None, end=' and ') print('Ceil is', ceil.data if ceil else None) |
The time complexity of the above solution is O(n), where n is the size of the BST, and requires space proportional to the tree’s height for the call stack.
Also See:
Fix a binary tree that is only one swap away from becoming a BST
Search a given key in BST – Iterative and Recursive Solution
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)