Implementing Ceil in BST

Given the root of a binary search tree and an integer key, return the ceil of key — the smallest value in the BST that is greater than or equal to key. If no such value exists, return -1.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Ceil is the smallest value that is >= key.

If the node is < key, only its right subtree can hold the ceil.

If the node is >= key, record it as a candidate and go left to try to find a smaller valid value.

Common doubts

A node >= key is valid, but a smaller value that's still >= key may sit in its left subtree — and we want the smallest.

When every value is smaller than key, so no candidate is ever recorded.

Floor is the largest value <= key: record when the node is <= key and go right instead.

Interview follow-ups

· What an interviewer asks next.

Mirror the logic: candidate when node <= key, then go right to find a larger valid value.

You'd have to scan all nodes (O(n)); the ordering is what makes it an O(height) descent.

Fun facts

Ceil and floor together let a BST answer 'nearest value' queries in O(height).
This best-candidate descent is the same shape as lower_bound / upper_bound on a sorted array.

Asked at

AmazonMicrosoftFlipkart

Frequently Sometimes Occasionally

Example 1

Input: root = [8, 4, 12, 2, 6, 10, 14], key = 5
Output: 6
The smallest value >= 5 in the tree is 6.

Example 2

Input: root = [8, 4, 12, 2, 6, 10, 14], key = 15
Output: -1
No value is >= 15.

Constraints

- The number of nodes is in the range [1, 10^5] - 1 <= Node.val <= 10^5 - root is a valid BST - 0 <= key <= 10^5

Ceil is a guided descent. At each node: if it equals the key, that's the ceil. If it's smaller than the key, it can't be the ceil, and only the right subtree holds larger values — go right. If it's greater than or equal, it's a valid candidate, so remember it and go left to look for an even smaller valid value. One walk down — O(height).

Prerequisites

Before you start

· Concepts used directly in the solution.

BST invariant. Left < node < right, everywhere.

Best-candidate walk. Track the best answer seen while descending.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definition

“What is the ceil?”

The smallest value that is >= key.

“What if key is larger than everything?”

Return -1 — no value qualifies.

The ideal opening — say it like this

Ceil is the smallest value at least key, so I descend, and whenever a node is >= key I record it as a candidate and go left to try to beat it.

When a node is smaller than key, only its right subtree can help, so I go right.

Understand the problem

Worked example — BST [8, 4, 12, 2, 6, 10, 14], key = 5

8 >= 5 -> candidate 8, go left
4 < 5  -> go right
6 >= 5 -> candidate 6, go left
(null) -> ceil = 6

Key observations

1Aha

Only >= values are candidates

A node smaller than the key can never be the ceil; its right subtree might hold one.

2Aha

Go left after a candidate

A recorded candidate might be beaten by a smaller valid value on its left.

3Aha

O(height)

It's one root-to-leaf descent — O(log n) balanced, O(n) worst case.

Brute force vs optimal

	Recursive descent	Iterative descent
Idea	Recurse the correct side, track candidate	Loop, track candidate
Time	O(height)	O(height)
Space	O(height)	O(1)

Both are the same O(height) walk. Full code is in the Approaches selector below.

Summary

Key takeaway

Descend the BST: v == key returns v; v < key go right; v >= key record v and go left. The last recorded value is the ceil (or -1). O(height), O(1) iterative.

while node:
    if v == key: return v
    if v < key: node = node.right
    else: ans = v; node = node.left