Floor in a Binary Search Tree
Given a BST and an integer x, find the floor of x: the largest value in the tree that is less than or equal to x. If no such value exists, return -1.
Intuition
1 82 / \3 4 124 / \ / \5 2 6 10 14Floor of 5 is 4, floor of 13 is 12, floor of 8 is 8, and floor of 1 is -1 (nothing in the tree is 1 or less).
Floor is the mirror of ceil. When the node is at most the key, it is a candidate and a bigger one might be in the right subtree, so remember it and go right. When the node is larger than the key, it cannot be the floor and neither can its right subtree, so go left.
Approach: Walk Down and Remember the Best Candidate
- Set
floor = -1. - While the node exists:
- If
node.data == x, returnx. - If
x > node.data, this node is a valid candidate: setfloor = node.dataand go right for a bigger one. - Otherwise go left.
- If
- Return
floor.
The candidate only ever gets bigger, because each update is followed by a move toward larger values.
Code
class Solution {public:int floor(Node* root, int x) {int floorVal = -1;while (root != nullptr) {if (root->data == x) return x;if (x > root->data) {floorVal = root->data;root = root->right;} else {root = root->left;}}return floorVal;}};
Complexity
Time: O(h)
One root-to-leaf path is walked: O(log n) balanced, O(n) skewed.
Space: O(1)
Only a few variables are used.
How to Explain It in an Interview
How to Explain it in an Interview
The 30-Second Spoken Pitch
"The floor is the largest value in the tree that is at most the key, and it is the mirror image of ceil. I walk down from the root with a stored candidate. If the node equals the key, I return it. If the key is larger than the node, the node is a valid candidate, so I store it and go right to look for a bigger one. If the node is larger than the key, it and its right subtree are too big, so I go left. When I run out of nodes I return the stored candidate, minus one if there was none. Time is O of h and space is O of one."
Next TopicInsert Into a Binary Search Tree