Log inSign up
mediumGeeksforGeeksNot Started

Ceil in BST

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given a Binary Search Tree (BST) and an integer key X, find the ceil of X in the BST.

The ceil of X is defined as the smallest value in the BST that is greater than or equal to X (val >= X). If no such value exists (i.e., all elements in the BST are smaller than X), return -1.

---

### Examples

Example 1: ```text 8 / \ 4 12 / \ 2 6

Input: root = [8, 4, 12, 2, 6], X = 5 Output: 6 Explanation: The nodes greater than or equal to 5 are 6, 8, and 12. The smallest among them is 6. ```

Example 2: ```text 8 / \ 4 12 / \ 2 6

Input: root = [8, 4, 12, 2, 6], X = 13 Output: -1 Explanation: All values in the BST are smaller than 13, so no ceil exists. ```

---

### Constraints - The number of nodes in the tree is in the range [1, 10^5]. - 1 <= Node.val <= 10^6 - 1 <= X <= 10^6

Constraints:

  • The number of nodes in the tree is in the range [1, 105].
  • 1 <= Node.val <= 106
  • 1 <= X <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the ceil definition in search trees (smallest value >= X).
  • Master the symmetric relationship between Floor and Ceil algorithms.
  • Implement the search with O(H) time and O(1) auxiliary space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding closest larger or equal element in a sorted tree structure
  • Target comparison where leftward traversal refines the candidate
  • Binary search decision tree matching

Algorithmic Decision Tree:

  • If curr.val == X -> return X immediately (exact match is optimal ceil).
  • If curr.val > X -> record candidate = curr.val and move left to search for smaller candidates.
  • If curr.val < X -> candidate cannot be here; move right.

Connected Patterns:

Floor in BSTSearch in a Binary Search TreeInorder Successor in BST

1. Inorder Traversal Array Scan

Intuition

Since in-order traversal yields elements in ascending order, the first element with value >= X is the ceil.

Algorithm

  1. Collect all tree values into a list using in-order traversal.
  2. Iterate through sorted values: if val >= X, return val.
  3. If no such value is found, return -1.

Inorder Array Scan for X = 5

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Inorder traversal produces sorted list: [2, 4, 6, 8, 12]
Visual state
Values and pointers at this exact step
array
S
[2, 4, 6, 8, 12]
0
Check / comparison
Collected
Decision / next transition
List ready
Why this step matters

Inorder traversal produces sorted list: [2, 4, 6, 8, 12].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 void inorder(TreeNode* root, std::vector<int>& arr) {
13 if (!root) return;
14 inorder(root->left, arr);
15 arr.push_back(root->val);
16 inorder(root->right, arr);
17 }
18public:
19 int findCeil(TreeNode* root, int X) {
20 std::vector<int> arr;
21 inorder(root, arr);
22 for (int v : arr) {
23 if (v >= X) return v;
24 }
25 return -1;
26 }
27};
28
29int main() {
30 TreeNode* root = new TreeNode(8);
31 root->left = new TreeNode(4);
32 root->right = new TreeNode(12);
33 root->left->left = new TreeNode(2);
34 root->left->right = new TreeNode(6);
35
36 Solution sol;
37 std::cout << "Ceil of 5: " << sol.findCeil(root, 5) << " (Expected: 6)\n";
38 std::cout << "Ceil of 13: " << sol.findCeil(root, 13) << " (Expected: -1)\n";
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N)

2. Recursive Binary Search Descent

Intuition

When root.val > X, root is a candidate, but left subtree might have a smaller value that is still >= X. Take the minimum of root.val and the left recursive call.

Algorithm

  1. If root is null, return -1.
  2. If root.val == X, return X.
  3. If root.val < X, return findCeil(root.right, X).
  4. If root.val > X:
  5. Call leftCeil = findCeil(root.left, X).
  6. Return leftCeil != -1 ? leftCeil : root.val.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 int findCeil(TreeNode* root, int X) {
13 if (!root) return -1;
14 if (root->val == X) return X;
15 if (root->val < X) return findCeil(root->right, X);
16
17 int leftCeil = findCeil(root->left, X);
18 return (leftCeil != -1) ? leftCeil : root->val;
19 }
20};
21
22int main() {
23 TreeNode* root = new TreeNode(8);
24 root->left = new TreeNode(4);
25 root->right = new TreeNode(12);
26 root->left->left = new TreeNode(2);
27 root->left->right = new TreeNode(6);
28
29 Solution sol;
30 std::cout << "Recursive Ceil 5: " << sol.findCeil(root, 5) << " (Expected: 6)\n";
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(H)
  • Space complexity: O(H)

3. Iterative Binary Search Descent (O(1) Space)

Intuition

At each node: if curr.val == X, return X. If curr.val > X, update ceilVal = curr.val and move curr = curr.left. If curr.val < X, move curr = curr.right. Zero stack frames.

Algorithm

  1. Initialize ceilVal = -1, curr = root.
  2. While curr is not null:
  3. If curr.val == X:
  4. Return X (exact match is optimal ceil).
  5. If curr.val > X:
  6. ceilVal = curr.val;
  7. curr = curr.left;
  8. Else (curr.val < X):
  9. curr = curr.right;
  10. Return ceilVal.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 int findCeil(TreeNode* root, int X) {
13 int ceilVal = -1;
14 TreeNode* curr = root;
15 while (curr) {
16 if (curr->val == X) {
17 return X;
18 }
19 if (curr->val > X) {
20 ceilVal = curr->val;
21 curr = curr->left;
22 } else {
23 curr = curr->right;
24 }
25 }
26 return ceilVal;
27 }
28};
29
30int main() {
31 TreeNode* root = new TreeNode(8);
32 root->left = new TreeNode(4);
33 root->right = new TreeNode(12);
34 root->left->left = new TreeNode(2);
35 root->left->right = new TreeNode(6);
36
37 Solution sol;
38 std::cout << "Iterative Ceil 5: " << sol.findCeil(root, 5) << " (Expected: 6)\n";
39 std::cout << "Iterative Ceil 13: " << sol.findCeil(root, 13) << " (Expected: -1)\n";
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(H)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Inorder Traversal Array ScanO(N)O(N)Collect all values in ascending order and find the first value >= X.Full traversal memory and time
2.Recursive Binary SearchO(H)O(H)Logarithmic path traversal with recursive call stack.Call stack frames
3.Iterative Binary SearchOptimalO(H)O(1)While loop maintaining ceil candidate when moving left.Tree height

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Moving right when curr.val > X, which looks at even larger values instead of finding the smallest qualifying value.

Pitfall 2:

Overwriting ceil candidate when moving right on curr.val < X.

Pitfall 3:

Confusing Floor and Ceil: Floor tracks when moving right (curr.val < X), Ceil tracks when moving left (curr.val > X).

Crucial Edge Cases to Validate:

  • X is greater than the maximum value in the BST — ceilVal remains -1 throughout the traversal, returning -1.
  • X matches an exact node value — Returns X immediately upon encountering curr.val == X.
  • X is smaller than the minimum value in the BST — Returns the minimum value in the BST (leftmost leaf).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Draw a small BST on the whiteboard and contrast Floor and Ceil side by side to demonstrate mastery of BST properties.
  2. Write the iterative solution directly — it is concise (10 lines) and demonstrates O(1) auxiliary space discipline.
  3. Clarify what value to return if no valid candidate exists (-1).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the definition of Ceil of X in a BST?

2.When curr.val > X, why do we move to curr.left?

3.What is returned if all keys in the BST are strictly smaller than X?

Back to DSA Sheet