On this page

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 8
2 / \
3 4 12
4 / \ / \
5 2 6 10 14

Ceil 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

  1. Set ceil = -1.
  2. While the node exists:
    • If node.data == key, return key. 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.data and go left to look for a smaller one.
  3. 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

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 ceil is the smallest value in the tree that is at least the key. I walk down from the root while remembering the best candidate. If the current node equals the key, that is the answer. If the key is larger than the node, the node and its left subtree are too small, so I go right. If the node is larger than the key, this node is a valid candidate, so I store it and go left, hoping for a smaller valid one. If I fall off the tree I return the stored candidate, which is minus one if I never found one. It follows one path, so time is O of h and space is O of one."
Next TopicFloor in a Binary Search Tree