The problem. Given the root of a binary search tree and a number x, return its floor — the largest value in the tree that is ≤ x — and its ceil — the smallest value that is ≥ x. If there is no such value, return -1 for it. Return them as [floor, ceil].
root = [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13]
x = 5 -> [4, 6]
x = 7 -> [7, 7] (x is in the tree)
x = 0 -> [-1, 1] (nothing is <= 0)
x = 20 -> [14, -1] (nothing is >= 20)Walk down as if searching for x. Every node you pass is a candidate: a node ≤ x is a possible floor, and the best floor so far is the most recent one (everything later is closer to x). Then go right, toward bigger values that might still be ≤ x. A node ≥ x is a possible ceil — go left. If you hit x itself, it's both.
function floorAndCeil(root, x) { const values = []; const walk = (node) => { if (node === null) return; walk(node.left); values.push(node.val); // in-order: sorted walk(node.right); }; walk(root); let floor = -1, ceil = -1; for (const v of values) { if (v <= x) floor = v; // the last one <= x if (v >= x && ceil === -1) ceil = v; // the first one >= x } return [floor, ceil];}Time O(n), space O(n). Correct, but it reads the whole tree for two values.
Smaller nodes are floor candidates (go right), bigger ones ceil candidates (go left).
function floorAndCeil(root, x) { let floor = -1, ceil = -1; let node = root; while (node !== null) { if (node.val === x) return [x, x]; // x itself is both if (node.val < x) { floor = node.val; // a floor candidate; bigger ones are to the right node = node.right; } else { ceil = node.val; // a ceil candidate; smaller ones are to the left node = node.left; } } return [floor, ceil];}Time O(h), space O(1). Why is the latest candidate always the best? After passing a floor candidate f you only go right, into values bigger than f; any further floor candidate is therefore closer to x. The same argument mirrored works for ceil.
lower_bound on a std::set do exactly this.