Pattern visualizer

Ceil in BST

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. 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..

Iterative candidate tracking while descending

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

Call stack

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

line 2

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

Where to practice BST

Practice BST problems All BST problems Back to roadmap