Problem statement

You are given the root of a binary search tree with distinct values and an integer x.

Return the ceil of x in the tree: the smallest node value that is greater than or equal to x. If every value is smaller than x, return -1.

Example 1

Input: root = [8,4,12,2,6,10,14], x = 5
Output: 6
Explanation: The values not below 5 are 6, 8, 10, 12 and 14; the smallest is 6.

Example 2

Input: root = [8,4,12,2,6,10,14], x = 14
Output: 14
Explanation: 14 is in the tree, so it is its own ceil.

Example 3

Input: root = [8,4,12,2,6,10,14], x = 15
Output: -1
Explanation: Every value is below 15.

Constraints

• 1 <= number of nodes <= 10^5
• 1 <= Node.val <= 10^5
• all node values are distinct
• 1 <= x <= 10^5

Hints for Ceil in BST

1. Hint 1

   Walk down from the root as in a search; the ordering tells you which side can hold better candidates.

2. Hint 2

   If a node's value is at least x, it is a candidate — and anything smaller that still qualifies is in its left subtree.

3. Hint 3

   If a node's value is below x, neither it nor its left subtree qualifies: go right. Keep the last candidate seen.

How to solve Ceil in BST

Search for x as usual. Every node where the walk turns left has a value ≥ x and is a candidate; each later candidate is smaller than the previous one, so the last one recorded is the ceil.

Approach

1. Set ceil = -1 and start at the root.
2. If the node's value equals x, return it.
3. If it is greater than x, record it as ceil and move left; otherwise move right.
4. When the walk falls off the tree, return ceil.

Why it works

When a node's value v is above x, its right subtree holds only values above v — never a better ceil — so the search narrows to the left. When v is below x, the node and its whole left subtree are below x and are excluded. The candidates recorded shrink each time, ending at the smallest value ≥ x.

Complexity

• Time — O(h)
• Space — O(1)

Pitfalls

• Return -1, not the largest value, when x exceeds every value in the tree.
• An exact match is its own ceil — return it at once.

Reference solution

Python

from typing import Optional

def findCeil(root: Optional[TreeNode], x: int) -> int:
    ceil = -1
    node = root
    while node is not None:
        if node.val == x:
            return x
        if node.val > x:
            ceil = node.val
            node = node.left
        else:
            node = node.right
    return ceil

Java

public static int findCeil(TreeNode root, int x) {
    int ceil = -1;
    TreeNode node = root;
    while (node != null) {
        if (node.val == x) return x;
        if (node.val > x) { ceil = node.val; node = node.left; }
        else node = node.right;
    }
    return ceil;
}

C++

int findCeil(TreeNode* root, int x) {
    int ceil = -1;
    TreeNode* node = root;
    while (node) {
        if (node->val == x) return x;
        if (node->val > x) { ceil = node->val; node = node->left; }
        else node = node->right;
    }
    return ceil;
}

JavaScript

var findCeil = function(root, x) {
    var ceil = -1, node = root;
    while (node !== null) {
        if (node.val === x) return x;
        if (node.val > x) { ceil = node.val; node = node.left; }
        else node = node.right;
    }
    return ceil;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More binary search problems

• Level of a Node in Binary Tree Easy
• Sum of Leaf Nodes at Minimum Level Easy
• Count BST Nodes That Lie in a Given Range Easy
• Nodes at Odd Levels Easy
• Kth Largest Element in BST Easy
• Nodes at Distance K from Root Easy