Ceil in BST
Ceil in BST is a easy trees & bst problem solved with the miscellaneous bst questions pattern.
The best approach, optimal (walk down the bst), runs in O(h) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from traverse everything up.
Problem
Given a BST and a value x, return the ceil of x in the tree: the smallest value that is greater than or equal to x, or -1 if there is none.
Examples
Example 1
- Input
root = [8, 5, 9, 1, 7, null, 10, null, 2, 6], x = 3- Output
5
Example 2
- Input
same tree, x = 11- Output
-1
Constraints
- The tree has
1to10^5nodes. - Return -1 if no value is >= x.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Traverse everything | O(n) | O(h) |
| Optimal (walk down the BST) | O(h) | O(1) |
1Traverse everything
O(n)O(h)Visit every node and keep the smallest value that is still >= x.
- DFS; track the minimum value >= x.
class Solution {
int findCeil(TreeNode root, int x) {
int best = Integer.MAX_VALUE;
Deque<TreeNode> st = new ArrayDeque<>();
if (root != null) st.push(root);
while (!st.isEmpty()) {
TreeNode n = st.pop();
if (n.val >= x) best = Math.min(best, n.val);
if (n.left != null) st.push(n.left);
if (n.right != null) st.push(n.right);
}
return best == Integer.MAX_VALUE ? -1 : best;
}
}class Solution:
def findCeil(self, root: Optional[TreeNode], x: int) -> int:
INT_MAX = 2**31 - 1
best = INT_MAX
st = []
if root is not None:
st.append(root)
while st:
n = st.pop()
if n.val >= x:
best = min(best, n.val)
if n.left is not None:
st.append(n.left)
if n.right is not None:
st.append(n.right)
return -1 if best == INT_MAX else bestclass Solution {
public:
int findCeil(TreeNode* root, int x) {
int best = INT_MAX;
stack<TreeNode*> st;
if (root != nullptr) st.push(root);
while (!st.empty()) {
TreeNode* n = st.top(); st.pop();
if (n->val >= x) best = min(best, n->val);
if (n->left != nullptr) st.push(n->left);
if (n->right != nullptr) st.push(n->right);
}
return best == INT_MAX ? -1 : best;
}
};function findCeil(root, x) {
const INT_MAX = 2147483647;
let best = INT_MAX;
const st = [];
if (root !== null) st.push(root);
while (st.length > 0) {
const n = st.pop();
if (n.val >= x) best = Math.min(best, n.val);
if (n.left !== null) st.push(n.left);
if (n.right !== null) st.push(n.right);
}
return best === INT_MAX ? -1 : best;
}2Optimal (walk down the BST)
O(h)O(1)Equal returns immediately. If the node is smaller than x, the ceil is to the right. Otherwise record it and look left for a smaller candidate.
- ans = -1.
- val == x → x. val < x → right. Else ans = val, left.
class Solution {
int findCeil(TreeNode root, int x) {
int ans = -1;
while (root != null) {
if (root.val == x) return x;
if (root.val < x) root = root.right;
else { ans = root.val; root = root.left; }
}
return ans;
}
}class Solution:
def findCeil(self, root: Optional[TreeNode], x: int) -> int:
ans = -1
while root is not None:
if root.val == x:
return x
if root.val < x:
root = root.right
else:
ans = root.val
root = root.left
return ansclass Solution {
public:
int findCeil(TreeNode* root, int x) {
int ans = -1;
while (root != nullptr) {
if (root->val == x) return x;
if (root->val < x) root = root->right;
else { ans = root->val; root = root->left; }
}
return ans;
}
};function findCeil(root, x) {
let ans = -1;
while (root !== null) {
if (root.val === x) return x;
if (root.val < x) root = root.right;
else { ans = root.val; root = root.left; }
}
return ans;
}Edge cases to test
- x equals a node value
- x above the maximum
Hints
Hint 1
A node >= x is a candidate; a smaller candidate may exist to its left.
FAQ
What is the best time complexity for Ceil in BST?
Optimal (walk down the BST) runs in O(h) time and O(1) extra space.
Which pattern does Ceil in BST use?
It is a trees & bst problem that uses the miscellaneous bst questions pattern. Other problems with the same pattern: Inorder Successor in BST, Inorder predecessor, Floor in BST.
Is there a brute force solution for Ceil in BST?
Yes. Traverse everything takes O(n) time and O(h) space. Visit every node and keep the smallest value that is still = x.
Which edge cases should I test for Ceil in BST?
x equals a node value; x above the maximum.