DSA Tracker

Visualize

Ceil in BST

Iterative candidate tracking while descending

time O(h) — O(log n) balanced, O(n) skewedspace O(1)

Ceiling is the mirror of floor. At each node, if its value equals x, that is the exact ceiling. If its value is greater than x, it is a valid candidate ceiling — but a tighter one may still exist in its left subtree, so record it and keep descending left. If its value is less than x, neither this node nor its left subtree can be the ceiling, so descend right without touching the candidate. No backtracking is needed: the single best candidate seen while descending IS the answer.

Details

Animated on: Given a binary search tree and an integer x, find the ceiling of x: the smallest value in the tree that is >= x. Return -1 if none exists.

Problem:Ceil in BSTEasy

Iterative candidate tracking while descending

step 1 / 13

0
2
3
4
5
6
7
8
9

Call stack

ceil(x=1)node → 6, ceil → -1

Initialize node at root 6 and ceil at -1 — no candidate ceiling found yet. Target x is 1.

Pseudocode
1node <- root
2ceil <- -1
3WHILE node != null:
4  IF node.val = x:
5    RETURN node.val
6  ELSE IF node.val > x:
7    ceil <- node.val
8    node <- node.left
9  ELSE:
10    node <- node.right
11RETURN ceil

← / → step · space play · Home restart

Every step in words

Show all 13 steps
  1. Initialize node at root 6 and ceil at -1 — no candidate ceiling found yet. Target x is 1.
  2. Is 6 > 1? Yes — 6 qualifies as a candidate ceiling, but a smaller one may still hide in its left subtree.
  3. ceil ← 6. This is now the tightest candidate seen so far.
  4. node ← node.left. Descend to 2 to check for an even tighter ceiling.
  5. node holds 2, which is non-null, so loop again and inspect it.
  6. Is 2 > 1? Yes — 2 qualifies as a candidate ceiling, but a smaller one may still hide in its left subtree.
  7. ceil ← 2. This is now the tightest candidate seen so far.
  8. node ← node.left. Descend to 0 to check for an even tighter ceiling.
  9. node holds 0, which is non-null, so loop again and inspect it.
  10. Is 0 > 1? No — 0 is too small to be a ceiling, and so is everything in its left subtree. The answer must lie to the right.
  11. node ← node.right, which is null. There is nothing further to check.
  12. node is now null — the loop condition fails and the walk ends.
  13. Return ceil = 2. Starting from 6, the walk narrowed the candidate from 6 to 2 and confirmed nothing smaller than 2 (but still >= 1) exists.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Ceil in BST in the editorAll BST problemsBack to roadmap