Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Ceil in BST

EASYProblemSolveExternal Links

Description

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

The ceil of x is defined as the smallest value in the tree that is greater than or equal to x. In other words, among all nodes whose values are at least x, the ceil is the one with the minimum value.

If no node in the BST has a value greater than or equal to x, return -1.

Examples

Example 1

Input:

       5
      / \
     1   7
      \
       2
        \
         3

x = 3

Output: 3

Explanation: The value 3 exists directly in the BST as a leaf node. Since 3 equals x, it is the smallest value that is greater than or equal to x. An exact match is always the tightest possible ceil.

Example 2

Input:

        10
       / \
      5   11
     / \
    4   7
         \
          8

x = 6

Output: 7

Explanation: The value 6 does not appear in the BST. The nodes with values greater than or equal to 6 are: 7, 8, 10, and 11. Among these, 7 is the smallest, making it the ceil of 6.

Constraints

  • 1 ≤ Number of nodes ≤ 10^5
  • 1 ≤ Value of nodes ≤ 10^5

Editorial

Brute Force

Intuition

The most natural starting point is to forget the tree structure entirely. If we had all the node values laid out in a sorted list, finding the ceil would be straightforward: just walk through the list and return the first value that is greater than or equal to x.

A BST has a very useful property — its inorder traversal produces values in ascending sorted order. So the plan is simple: perform an inorder traversal to collect every value into a sorted array, then scan that array from left to right until we find the first value that satisfies our condition.

Think of it like emptying a jar of numbered marbles onto a table, lining them up from smallest to largest, and then walking along the line until you find the first marble whose number is at least as large as the one you are looking for.

Step-by-Step Explanation

Let us trace through the algorithm using the BST from Example 2 with x = 6:

Step 1: Perform an inorder traversal of the BST. Starting from the root (10), we recursively visit left subtree → node → right subtree. This yields all values in ascending order.

  • Inorder result: [4, 5, 7, 8, 10, 11]

Step 2: Scan the sorted array from left to right.

  • Check arr[0] = 4. Is 4 ≥ 6? No. 4 is too small. Move forward.

Step 3: Check arr[1] = 5. Is 5 ≥ 6? No. Still too small. Continue.

Step 4: Check arr[2] = 7. Is 7 ≥ 6? Yes! This is the first value in sorted order that is greater than or equal to 6.

Step 5: Return 7 as the ceil of 6. Since the array is sorted in ascending order, the first value ≥ x is guaranteed to be the smallest such value.

Scanning Sorted Inorder Array for Ceil of 6 — After performing inorder traversal to get sorted values, we scan left to right looking for the first value greater than or equal to x.

Algorithm

  1. Perform an inorder traversal of the BST to collect all node values into a sorted array
  2. Scan the sorted array from left to right:
    • For each value, check if it is ≥ x
    • If yes, return that value immediately (it is the ceil)
  3. If no value ≥ x is found after scanning the entire array, return -1

Code

#include <vector>
using namespace std;

// Collect all node values in sorted order via inorder traversal
void inorder(Node* node, vector<int>& result) {
    if (node == nullptr) return;
    inorder(node->left, result);
    result.push_back(node->data);
    inorder(node->right, result);
}

int findCeil(Node* root, int x) {
    vector<int> sorted;
    inorder(root, sorted);
    
    // Scan for the first value >= x
    for (int val : sorted) {
        if (val >= x) {
            return val;
        }
    }
    return -1;  // No ceil exists
}
def findCeil(root, x):
    sorted_vals = []
    
    # Inorder traversal gives sorted values for a BST
    def inorder(node):
        if node is None:
            return
        inorder(node.left)
        sorted_vals.append(node.data)
        inorder(node.right)
    
    inorder(root)
    
    # Scan for first value >= x
    for val in sorted_vals:
        if val >= x:
            return val
    return -1
import java.util.ArrayList;
import java.util.List;

int findCeil(Node root, int x) {
    List<Integer> sorted = new ArrayList<>();
    inorder(root, sorted);
    
    // Scan for first value >= x
    for (int val : sorted) {
        if (val >= x) {
            return val;
        }
    }
    return -1;
}

void inorder(Node node, List<Integer> result) {
    if (node == null) return;
    inorder(node.left, result);
    result.add(node.data);
    inorder(node.right, result);
}

Complexity Analysis

Time Complexity: O(n)

The inorder traversal visits every node in the BST exactly once, which takes O(n) time. Then the linear scan over the sorted array takes up to O(n) in the worst case. Combined, the total time is O(n) + O(n) = O(n).

Space Complexity: O(n)

We store all n node values in an auxiliary array. Additionally, the recursion stack for the inorder traversal uses O(h) space where h is the tree height. Since h ≤ n, the dominant space cost is the O(n) array.

Why This Approach Is Not Efficient

The brute force visits every single node in the tree and stores all values in a separate array. For a BST with up to 10^5 nodes, we allocate space for 10^5 integers and perform up to 10^5 comparisons.

This completely ignores the fundamental property of a BST: for any node, all values in the left subtree are smaller and all values in the right subtree are larger. This ordering means we should be able to eliminate entire subtrees at each step instead of examining every node.

Think about it: if the root holds the value 10 and we need the ceil of 6, we know the entire right subtree (values > 10) contains values that are all too large to be the tightest ceil. There is no reason to visit them at all. Similarly, if a node holds value 5 and our target is 6, the entire left subtree (values < 5) is irrelevant since all those values are less than 6.

The key insight is that at each node we can make a binary decision — go left or go right — pruning roughly half the remaining tree at each step. This is analogous to binary search on a sorted array and reduces the number of nodes visited from n to at most h (the height of the tree).

Optimal Approach - Iterative BST Traversal

Intuition

Instead of collecting all values and scanning them, we can leverage the BST property to guide our search directly. Starting from the root, we make a simple binary decision at each node:

  • If the current node's value equals x: We have found the exact ceil. No smaller valid value exists — return immediately.
  • If the current node's value is less than x: This node is too small to be the ceil. All values in its left subtree are even smaller (BST property), so they are all irrelevant. Move to the right child where larger values live.
  • If the current node's value is greater than x: This node is a valid ceil candidate — it is ≥ x. But a tighter (smaller) valid value might exist in the left subtree. Record this node as our best answer so far and move to the left child to search for a closer match.

We keep descending until we hit a null pointer, at which point the last recorded candidate is our answer.

Imagine searching for a restaurant that opens at or after 6 PM in a building where floors are sorted by opening time. If the current floor opens at 5 PM (too early), you go up. If it opens at 8 PM (valid but possibly not the closest), you note it and go down to check if a closer option exists. This narrowing process finds the tightest match without checking every floor.

Step-by-Step Explanation

Let us trace through the algorithm using the BST from Example 2 with x = 6:

Step 1: Start at the root node (value 10). Initialize ceil = -1.

  • Compare: x = 6 vs node = 10. Since 6 < 10, node 10 is ≥ x and qualifies as a ceil candidate.
  • Update ceil = 10. Move to the left child to search for a smaller valid ceil.

Step 2: Current node is 5.

  • Compare: x = 6 vs node = 5. Since 6 > 5, node 5 is too small to be the ceil.
  • Do not update ceil. Move to the right child where larger values exist.

Step 3: Current node is 7.

  • Compare: x = 6 vs node = 7. Since 6 < 7, node 7 is ≥ x and qualifies as a ceil candidate.
  • Update ceil = 7 (tighter than the previous candidate of 10). Move to the left child.

Step 4: Node 7 has no left child — we reach null. Traversal ends.

Step 5: Return ceil = 7. We visited only 3 nodes (10 → 5 → 7) out of 6 total, following a single root-to-leaf path. Nodes 4, 8, and 11 were never examined — the BST property allowed us to prune them entirely.

Ceil in BST — Iterative Traversal for x = 6 — Watch how the BST property guides us along a single root-to-leaf path, updating the ceil candidate whenever we find a node ≥ x and pruning irrelevant subtrees.

Algorithm

  1. Initialize ceil = -1 (no candidate found yet)
  2. While the current node is not null:
    • If current node's value equals x → return x (exact match, tightest possible ceil)
    • If x < current node's value → update ceil to current node's value, move to left child (search for a tighter candidate)
    • If x > current node's value → move to right child (need a larger value)
  3. Return ceil

Code

int findCeil(Node* root, int x) {
    int ceil = -1;
    
    while (root != nullptr) {
        // Exact match is the tightest possible ceil
        if (root->data == x) {
            return x;
        }
        
        if (x < root->data) {
            // Current node >= x, record as candidate
            ceil = root->data;
            // Search left for a smaller valid value
            root = root->left;
        } else {
            // Current node < x, need a larger value
            root = root->right;
        }
    }
    
    return ceil;
}
def findCeil(root, x):
    ceil = -1
    
    while root is not None:
        # Exact match is the tightest possible ceil
        if root.data == x:
            return x
        
        if x < root.data:
            # Current node >= x, record as candidate
            ceil = root.data
            # Search left for a smaller valid value
            root = root.left
        else:
            # Current node < x, need a larger value
            root = root.right
    
    return ceil
int findCeil(Node root, int x) {
    int ceil = -1;
    
    while (root != null) {
        // Exact match is the tightest possible ceil
        if (root.data == x) {
            return x;
        }
        
        if (x < root.data) {
            // Current node >= x, record as candidate
            ceil = root.data;
            // Search left for a smaller valid value
            root = root.left;
        } else {
            // Current node < x, need a larger value
            root = root.right;
        }
    }
    
    return ceil;
}

Complexity Analysis

Time Complexity: O(h), where h is the height of the BST

At each step we descend one level in the tree, making at most h comparisons before reaching a null pointer. For a balanced BST, h = O(log n), so the search runs in logarithmic time. For a skewed BST (essentially a linked list), h = O(n), which degenerates to linear time. On average for a random BST, h ≈ O(log n).

Space Complexity: O(1)

We use only a single integer variable (ceil) and a pointer to traverse the tree. No auxiliary data structures, no recursion stack. This is a constant-space solution regardless of tree size.