Floor and Ceil in BST in DSA Javascript

Mental Model

Floor is the biggest value smaller or equal to target; ceil is the smallest value bigger or equal to target in the BST.

Analogy: Imagine a ladder with numbered steps. Floor is the highest step you can stand on without going above your target number. Ceil is the lowest step you must climb to reach or pass your target.

       8
      / \
     4   12
    / \   / \
   2   6 10  14

Dry Run Walkthrough

Input: BST: 8->4->12->2->6->10->14, find floor and ceil of 5

Goal: Find the floor (largest ≤5) and ceil (smallest ≥5) in the BST

Step 1: Start at root node 8, compare 5 with 8

Current node: 8

Why: We start from the root to decide which subtree to explore

Step 2: Since 5 < 8, move to left child 4; update ceil candidate to 8

Current node: 4, ceil candidate: 8

Why: 5 is less than 8, so ceil could be 8 or smaller; floor must be ≤5

Step 3: Compare 5 with 4; since 5 > 4, move to right child 6; update floor candidate to 4

Current node: 6, floor candidate: 4, ceil candidate: 8

Why: 5 is greater than 4, so floor could be 4 or higher; ceil still 8

Step 4: Compare 5 with 6; since 5 < 6, move to left child which is null; update ceil candidate to 6

Current node: null, floor candidate: 4, ceil candidate: 6

Why: 5 is less than 6, so ceil could be 6; no left child means stop

Step 5: No more nodes to visit; floor is 4, ceil is 6

Floor: 4, Ceil: 6

Why: We found the closest smaller and larger values around 5

Result:

Floor: 4
Ceil: 6

Annotated Code

DSA Javascript

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(val) {
    const newNode = new Node(val);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let curr = this.root;
    while (true) {
      if (val < curr.val) {
        if (!curr.left) {
          curr.left = newNode;
          return;
        }
        curr = curr.left;
      } else {
        if (!curr.right) {
          curr.right = newNode;
          return;
        }
        curr = curr.right;
      }
    }
  }

  floorCeil(target) {
    let floor = null;
    let ceil = null;
    let curr = this.root;
    while (curr) {
      if (curr.val === target) {
        floor = curr.val;
        ceil = curr.val;
        break;
      } else if (target < curr.val) {
        ceil = curr.val; // update ceil candidate
        curr = curr.left; // go left to find smaller or equal
      } else {
        floor = curr.val; // update floor candidate
        curr = curr.right; // go right to find bigger or equal
      }
    }
    return { floor, ceil };
  }
}

// Driver code
const bst = new BST();
[8,4,12,2,6,10,14].forEach(v => bst.insert(v));
const target = 5;
const { floor, ceil } = bst.floorCeil(target);
console.log(`Floor: ${floor}`);
console.log(`Ceil: ${ceil}`);

while (curr) {

loop to traverse nodes until no more candidates

if (curr.val === target) {

exact match found, floor and ceil are target

else if (target < curr.val) {

target less than current, update ceil and go left

ceil = curr.val; // update ceil candidate

record current node as possible ceil

curr = curr.left; // go left to find smaller or equal

move left to find closer ceil or floor

else {

target greater than current, update floor and go right

floor = curr.val; // update floor candidate

record current node as possible floor

curr = curr.right; // go right to find bigger or equal

move right to find closer floor or ceil

Output

Floor: 4

Ceil: 6

Complexity Analysis

Time: O(h) where h is the height of the BST because we traverse from root down to a leaf at most once

Space: O(1) because we use only a few variables for tracking floor, ceil, and current node

vs Alternative: Compared to scanning all nodes (O(n)), this approach is faster because BST properties let us skip large parts of the tree

Edge Cases

target smaller than all nodes

floor remains null, ceil is the smallest node

DSA Javascript

ceil = curr.val; // update ceil candidate

target larger than all nodes

ceil remains null, floor is the largest node

DSA Javascript

floor = curr.val; // update floor candidate

target equals a node value

floor and ceil both equal target value

DSA Javascript

if (curr.val === target) {

When to Use This Pattern

When asked to find closest smaller or larger values around a target in a BST, use floor and ceil search by moving left or right based on comparisons.

Common Mistakes

Mistake: Not updating floor or ceil candidates correctly when moving left or right
Fix: Update floor when moving right (target > current), update ceil when moving left (target < current)

Mistake: Stopping search too early without checking all possible candidates
Fix: Continue traversal until no more nodes to ensure closest floor and ceil are found

Summary

Finds the closest smaller or equal (floor) and closest larger or equal (ceil) values to a target in a BST.

Use when you need nearest bounds around a value efficiently in a sorted tree.

The key is to move left or right updating floor or ceil candidates based on comparisons until no nodes remain.