Why Floor and Ceil in BST in DSA Javascript?

The Big Idea

What if you could find the closest smaller or bigger number instantly without checking every single one?

The Scenario

Imagine you have a sorted list of numbers on paper, and you want to find the closest number less than or equal to a target (floor), or the closest number greater than or equal to the target (ceil). Doing this by scanning the list every time is slow and tiring.

The Problem

Manually scanning a list for floor or ceil means checking each number one by one. This takes a lot of time if the list is long. It's easy to make mistakes, like missing the closest number or mixing up floor and ceil.

The Solution

A Binary Search Tree (BST) organizes numbers so you can quickly find floor and ceil by moving left or right based on comparisons. This saves time and reduces errors by following a clear path instead of guessing.

Before vs After

✗ Before

function findFloor(arr, target) {
  let floor = null;
  for (let num of arr) {
    if (num <= target && (floor === null || num > floor)) {
      floor = num;
    }
  }
  return floor;
}

✓ After

function findFloorInBST(root, target) {
  let floor = null;
  let current = root;
  while (current !== null) {
    if (current.value === target) return current.value;
    if (current.value < target) {
      floor = current.value;
      current = current.right;
    } else {
      current = current.left;
    }
  }
  return floor;
}

What It Enables

It enables lightning-fast searches for closest smaller or larger values in sorted data, making programs smarter and faster.

Real Life Example

When booking flights, finding the closest cheaper or slightly more expensive ticket quickly helps you decide the best option without checking every price manually.

Key Takeaways

Manual search for floor and ceil is slow and error-prone.

BST structure allows quick navigation to find floor and ceil efficiently.

Using BST for floor and ceil saves time and reduces mistakes in large data.