Why Floor and Ceil in BST in DSA C++?

The Big Idea

What if you could find the closest number to your target 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 to find 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 jump to the part of the tree that might have the floor or ceil. This way, you don't check every number, just a few steps, making it fast and reliable.

Before vs After

✗ Before

int floor = INT_MIN;
for (int num : sortedList) {
  if (num <= target) floor = num;
}

✓ After

int floor = findFloor(root, target);

What It Enables

This lets you quickly find the closest smaller or larger number to any target, enabling fast decisions and searches in sorted data.

Real Life Example

When booking a flight, you want the closest cheaper or slightly more expensive ticket than your budget. Floor and ceil in BST help find these prices fast.

Key Takeaways

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

BST structure speeds up finding floor and ceil efficiently.

Floor and ceil help find closest smaller or larger values quickly.