Smallest Stored Value That Is Not Below a Number

Medium20–25 min

Topics

Binary Search TreeBSTCeilingSearch

Companies

AmazonMicrosoftFlipkartSamsung

You are given the root of a binary search tree with distinct values and an integer x. Return the smallest value in the tree that is greater than or equal to x (the "ceiling" of x). If every value in the tree is smaller than x, or the tree is empty, return -1.

Listing all values in order works, but the search-tree property lets you find the answer by walking a single path from the root and remembering the best candidate so far.

Test Case 1:

Input:root = [60, 25, 85, 10, 40, 70, 95, null, null, 35, 50], x = 38

Output:40

Explanation:The values ≥ 38 are 40, 50, 60, 70, 85 and 95; the smallest is 40.

Test Case 2:

Input:root = [60, 25, 85, 10, 40, 70, 95, null, null, 35, 50], x = 99

Output:-1

Explanation:The largest value in the tree is 95, which is below 99.

Test Case 3:

Input:root = [60, 25, 85, 10, 40, 70, 95, null, null, 35, 50], x = 70

Output:70

Explanation:x itself is in the tree, and equal counts.

Constraints

◆0 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000
◆The tree is a binary search tree (left subtree smaller, right subtree larger at every node), given by its root node
◆0 ≤ x ≤ 1000
◆Return the smallest value in the tree that is greater than or equal to x (x itself counts). If every value is smaller than x, or the tree is empty, return -1

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — List All Values in Order, Then Find the First Big Enough

Brute

An inorder walk of a binary search tree visits the values in ascending order. Collect them all in a list, then scan from the smallest: the first value that is ≥ x is the smallest such value. If none qualifies, the answer is -1. It always builds the full list of n values: O(n) time and O(n) space.

TimeO(n)

SpaceO(n)

Java

Try it out

class Solution {
    public int ceilOf(TreeNode root, int x) {
        List<Integer> vals = new ArrayList<>();
        inorder(root, vals);
        for (int v : vals) {
            if (v >= x) return v;
        }
        return -1;
    }

    private void inorder(TreeNode node, List<Integer> vals) {
        if (node == null) return;
        inorder(node.left, vals);
        vals.add(node.val);
        inorder(node.right, vals);
    }
}

Optimal — Walk Down Once, Remembering the Best Candidate

Optimal

Walk down from the root, keeping best = the smallest value seen so far that is ≥ x (initially -1). If the current node equals x, that is the answer. If it is larger than x, it is a valid candidate — record it — and anything better must be smaller, so go LEFT. If it is smaller than x it is too small, and its whole left subtree is smaller still, so go RIGHT. When the walk runs off the tree, best holds the answer. Only one path is followed: O(h) time, O(1) space.

TimeO(h)

SpaceO(1)