Floor and Ceil in BST in DSA Typescript

Mental Model

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

Analogy: Imagine a bookshelf sorted by book height. Floor is the tallest book not taller than your target height; ceil is the shortest book not shorter than your target height.

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

Dry Run Walkthrough

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

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

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

Current node: 8

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

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

Current node: 4, ceil=8

Why: Since 5 < 8, 8 is a candidate ceil; floor unknown yet

Step 3: 5 > 4, move to right child 6; update floor to 4

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

Why: Since 5 > 4, 4 is a candidate floor; check right subtree for closer values

Step 4: 5 < 6, move to left child null; update ceil to 6

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

Why: Since 5 < 6, 6 is a better ceil candidate; no left child means stop

Result:

Floor: 4
Ceil: 6

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function floorInBST(root: TreeNode | null, target: number): number | null {
  let floor: number | null = null;
  let curr = root;
  while (curr !== null) {
    if (curr.val === target) {
      return curr.val; // exact match is floor
    } else if (curr.val < target) {
      floor = curr.val; // update floor
      curr = curr.right; // try to find closer floor
    } else {
      curr = curr.left; // go left to find smaller values
    }
  }
  return floor;
}

function ceilInBST(root: TreeNode | null, target: number): number | null {
  let ceil: number | null = null;
  let curr = root;
  while (curr !== null) {
    if (curr.val === target) {
      return curr.val; // exact match is ceil
    } else if (curr.val > target) {
      ceil = curr.val; // update ceil
      curr = curr.left; // try to find closer ceil
    } else {
      curr = curr.right; // go right to find bigger values
    }
  }
  return ceil;
}

// Build BST from example
const root = new TreeNode(8,
  new TreeNode(4,
    new TreeNode(2),
    new TreeNode(6)
  ),
  new TreeNode(12,
    new TreeNode(10),
    new TreeNode(14)
  )
);

const target = 5;
const floorValue = floorInBST(root, target);
const ceilValue = ceilInBST(root, target);
console.log(`Floor: ${floorValue}`);
console.log(`Ceil: ${ceilValue}`);

while (curr !== null) {

Traverse nodes until no more to check

if (curr.val === target) { return curr.val; }

Exact match found, return immediately

else if (curr.val < target) { floor = curr.val; curr = curr.right; }

Update floor and move right to find closer floor

else { curr = curr.left; }

Move left to find smaller values

else if (curr.val > target) { ceil = curr.val; curr = curr.left; }

Update ceil and move left to find closer ceil

else { curr = curr.right; }

Move right to find bigger values

Output

Floor: 4

Ceil: 6

Complexity Analysis

Time: O(h) because we traverse from root down to leaf at most once, where h is tree height

Space: O(1) because we use only a few variables, no extra data structures

vs Alternative: Compared to scanning all nodes O(n), this uses BST property to reduce search to O(h)

Edge Cases

target smaller than all nodes

floor returns null, ceil returns smallest node

DSA Typescript

return floor;

target larger than all nodes

floor returns largest node, ceil returns null

DSA Typescript

return ceil;

target equals a node value

floor and ceil both return that node value immediately

DSA Typescript

if (curr.val === target) { return curr.val; }

When to Use This Pattern

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

Common Mistakes

Mistake: Not updating floor or ceil before moving to child nodes
Fix: Always update floor or ceil when current node is a valid candidate before moving

Mistake: Searching entire tree instead of using BST property
Fix: Use BST ordering to decide left or right subtree to explore

Summary

Find 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 for a value in a sorted tree structure.

The key is to update floor or ceil candidates while moving down the tree using BST ordering.

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 definition of floor in BST

   The floor of a value in BST is the greatest value 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 ceil, not floor. Options C and D are unrelated to floor concept.

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 TypeScript function signatures correctly represents a function to find the ceil in a BST?

easy

A. function findCeil(key: number, root: TreeNode): number

B. function findCeil(root: TreeNode | null, key: number): number | null

C. function findCeil(root: TreeNode, key: string): number

D. function findCeil(root: TreeNode | null): number

Solution

1. Step 1: Check parameter order and types

   Function should accept root node (possibly null) and a key number to find ceil for.

2. Step 2: Validate return type

   Return type should be number or null if no ceil found. function findCeil(root: TreeNode | null, key: number): number | null matches this.

3. Final Answer:

   function findCeil(root: TreeNode | null, key: number): number | null -> Option B

4. Quick Check:

   Correct params and return type [OK]

Hint: Root first, key second, return number or null [OK]

Common Mistakes:

• Swapping parameter order
• Using wrong parameter types
• Missing null in root type

3. Given the BST below and key = 14, what is the ceil value?

       10
      /  \
     5    15
         /  \
        12   20

medium

A. 12

B. 20

C. 15

D. null

Solution

1. Step 1: Locate key 14 in BST or nearest nodes

   14 is not in BST. Check nodes greater than or equal to 14: 15 and 20.

2. Step 2: Find smallest node ≥ 14

   Between 15 and 20, 15 is smaller and ≥ 14, so ceil is 15.

3. Final Answer:

   15 -> Option C

4. Quick Check:

   Ceil = smallest ≥ 14 is 15 [OK]

Hint: Ceil is smallest value ≥ key in BST [OK]

Common Mistakes:

• Choosing 12 which is less than 14
• Choosing 20 which is larger but not smallest ≥ 14
• Returning null when ceil exists

4. Consider this TypeScript function to find floor in BST:

function findFloor(root: TreeNode | null, key: number): number | null {
  if (!root) return null;
  if (root.val === key) return root.val;
  const floorRight = findFloor(root.right, key);
  return floorRight !== null ? floorRight : root.val;
}

What is the bug in this code?

medium

A. It returns root.val even if floorRight is null and root.val > key

B. It does not check for null root

C. It returns key instead of floor value

D. It incorrectly calls findFloor on root.left when root.val < key

Solution

1. Step 1: Identify missing logic for root.val > key

   The code does not recurse into the left subtree when root.val > key. Instead, it always computes floorRight from the right subtree.

2. Step 2: Trace buggy return

   When root.val > key and right subtree yields null for floorRight (common case), it returns root.val which exceeds key, violating floor definition.

3. Final Answer:

   It returns root.val even if floorRight is null and root.val > key -> Option A

4. Quick Check:

   Missing left recursion on root.val > key [OK]

Hint: Check return when right subtree floor is null [OK]

Common Mistakes:

• Ignoring null checks
• Confusing left and right subtree calls
• Assuming root.val always valid floor

5. You have a BST with values [8, 4, 12, 2, 6, 10, 14]. You want to find the floor and ceil of 5. Which pair is correct?

medium

A. Floor = 2, Ceil = 8

B. Floor = 6, Ceil = 4

C. Floor = 5, Ceil = 5

D. Floor = 4, Ceil = 6

Solution

1. Step 1: Identify floor of 5 in BST

   Floor is greatest value ≤ 5. Values ≤ 5 are 2 and 4. Greatest is 4.

2. Step 2: Identify ceil of 5 in BST

   Ceil is smallest value ≥ 5. Values ≥ 5 are 6, 8, 10, 12, 14. Smallest is 6.

3. Final Answer:

   Floor = 4, Ceil = 6 -> Option D

4. Quick Check:

   Floor ≤ 5 = 4, Ceil ≥ 5 = 6 [OK]

Hint: Floor ≤ key, Ceil ≥ key; pick closest values [OK]

Common Mistakes:

• Swapping floor and ceil values
• Assuming floor or ceil equals key if not present
• Choosing values not in BST