Why Floor and Ceil in BST in DSA Typescript?

The Big Idea

What if you could find the closest match in a huge list without checking every item?

The Scenario

Imagine you have a big phone book sorted by names. You want to find the closest name that is just before or just after a name you have in mind, but you don't want to look through every single page.

The Problem

Looking through the phone book page by page is slow and tiring. You might miss the closest name or take too long to find it. It's easy to get lost or confused when the list is very long.

The Solution

Using a special tree called a Binary Search Tree (BST), you can quickly jump to the closest smaller or larger name. The BST keeps names sorted, so you can find the floor (closest smaller or equal) and ceil (closest larger or equal) fast without checking every name.

Before vs After

✗ Before

let closestFloor = null;
for (let name of phoneBook) {
  if (name <= targetName && (closestFloor === null || name > closestFloor)) {
    closestFloor = name;
  }
}

✓ After

function findFloor(node, target) {
  if (!node) return null;
  if (node.value === target) return node.value;
  if (node.value > target) return findFloor(node.left, target);
  let floorRight = findFloor(node.right, target);
  return floorRight !== null ? floorRight : node.value;
}

What It Enables

This lets you find the closest smaller or larger value quickly, making searching smarter and faster in sorted data.

Real Life Example

When booking flights, you might want to find the closest earlier or later flight time to your preferred time. Floor and ceil in BST help find these times instantly.

Key Takeaways

Manual search is slow and error-prone for finding closest smaller or larger values.

Floor and ceil in BST use the tree's order to find these values quickly.

This makes searching in sorted data fast and efficient.