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.

Practice

1. What does the floor of a value in a Binary Search Tree (BST) represent?

easy

A. The greatest value in the BST less than or equal to the given value

B. The smallest value in the BST greater than or equal to the given value

C. The root value of the BST

D. The average of all values in the BST

Solution

1. Step 1: Understand the floor concept in BST

   The floor of a value is the largest value in the BST that is less than or equal to the given value.

2. Step 2: Compare with other options

   The smallest value in the BST greater than or equal to the given value describes the ceil, not the floor. Options C and D are unrelated to floor.

3. Final Answer:

   The greatest value in the BST less than or equal to the given value -> Option A

4. Quick Check:

   Floor = greatest ≤ value [OK]

Hint: Floor is largest value ≤ target in BST [OK]

Common Mistakes:

• Confusing floor with ceil
• Thinking floor is the smallest value
• Assuming floor is always the root

2. Which of the following is the correct JavaScript function signature to find the ceil of a value in a BST?

easy

A. function ceilFind(value, root) {}

B. function findFloor(value) {}

C. function findCeil(root, value) {}

D. function ceil(root) {}

Solution

1. Step 1: Identify correct parameter order and naming

   The function to find ceil should take the BST root and the target value as parameters, typically as (root, value).

2. Step 2: Check options for correct signature

   function findCeil(root, value) {} matches this pattern. function ceilFind(value, root) {} reverses parameters, C is for floor and missing root, D misses value parameter.

3. Final Answer:

   function findCeil(root, value) {} -> Option C

4. Quick Check:

   Correct params: root, value [OK]

Hint: Function needs root and value parameters [OK]

Common Mistakes:

• Swapping parameter order
• Missing root or value parameter
• Using wrong function name

3. Given the BST below and value = 14, what is the floor of 14?

       15
      /  \
     10  20
    /  \   \
   8   12  25

medium

A. 15

B. 10

C. 14

D. 12

Solution

1. Step 1: Locate floor value in BST for 14

   Floor is greatest value ≤ 14. Values ≤ 14 are 8, 10, 12. 12 is the greatest among these.

2. Step 2: Confirm no value closer to 14 exists

   15 is greater than 14, so not floor. 14 is not in BST.

3. Final Answer:

   12 -> Option D

4. Quick Check:

   Floor(14) = 12 [OK]

Hint: Floor ≤ value, pick largest such node [OK]

Common Mistakes:

• Choosing 15 which is > 14
• Assuming floor must be exact value
• Picking smaller values like 10 instead of 12

4. Consider this buggy JavaScript code to find ceil in BST:

function findCeil(root, value) {
  if (!root) return -1;
  if (root.val === value) return root.val;
  if (root.val < value) return findCeil(root.right, value);
  let ceil = findCeil(root.left, value);
  return (ceil >= value) ? ceil : root.val;
}

What is the main error?

medium

A. It searches left subtree when root.val < value instead of right

B. It returns -1 when root is null instead of null

C. It compares ceil with value incorrectly

D. It does not handle root.val === value case

Solution

1. Step 1: Analyze subtree traversal logic

   If root.val < value, ceil must be in right subtree, but code wrongly searches left subtree.

2. Step 2: Check other parts

   Return -1 is acceptable as sentinel. Comparison and equality check are correct.

3. Final Answer:

   It searches left subtree when root.val < value instead of right -> Option A

4. Quick Check:

   Wrong subtree chosen for root.val < value [OK]

Hint: Go right if root.val < value for ceil [OK]

Common Mistakes:

• Searching wrong subtree
• Ignoring base case
• Incorrect comparison logic

5. You want to find both floor and ceil of value 17 in this BST:

       16
      /  \
     10  20
    /  \   \
   8   12  25

Which pair is correct?

hard

A. [16, 17]

B. [16, 20]

C. [17, 20]

D. [15, 20]

Solution

1. Step 1: Find floor of 17

   Floor is greatest value ≤ 17. Values ≤ 17 are 8, 10, 12, 16. Largest is 16.

2. Step 2: Find ceil of 17

   Ceil is smallest value ≥ 17. Values ≥ 17 are 20, 25. Smallest is 20.

3. Final Answer:

   [16, 20] -> Option B

4. Quick Check:

   Floor=16, Ceil=20 [OK]

Hint: Floor ≤ value, ceil ≥ value, pick closest [OK]

Common Mistakes:

• Assuming floor or ceil equals value if not present
• Choosing wrong subtree values
• Mixing floor and ceil values