Ceil in a Binary Search Tree
Given a BST and an integer key, find the ceil of key: the smallest value in the tree that is greater than or equal to key. If no such value exists, return -1.
Intuition
1 82 / \3 4 124 / \ / \5 2 6 10 14Ceil of 5 is 6, ceil of 13 is 14, ceil of 8 is 8, and ceil of 15 is -1 (nothing in the tree is 15 or more).
Recall the BST property: for every node, everything in the left subtree is smaller and everything in the right subtree is larger. Because of it, one comparison at a node tells us which half of the tree to ignore.
When we stand on a node whose value is at least the key, that node is a candidate for the ceil, but a smaller candidate might hide in the left subtree, so we remember it and go left. When the node is smaller than the key, it cannot be the ceil and neither can anything on its left, so we go right.
Approach: Walk Down and Remember the Best Candidate
- Set
ceil = -1. - While the node exists:
- If
node.data == key, returnkey. Nothing can beat an exact match. - If
key > node.data, the answer is somewhere to the right, so go right. - Otherwise this node is a valid candidate: set
ceil = node.dataand go left to look for a smaller one.
- If
- Return
ceil.
The candidate only ever gets smaller, because each time we update it we move to a smaller side.
Code
class Solution {public:int findCeil(Node* root, int key) {int ceil = -1;while (root != nullptr) {if (root->data == key) return key;if (key > root->data) {root = root->right;} else {ceil = root->data;root = root->left;}}return ceil;}};
Complexity
One root-to-leaf path is walked: O(log n) balanced, O(n) skewed.
Only a few variables are used.