Why Floor and Ceil in BST in DSA Go?

The Big Idea

Discover how to find the closest match in sorted data instantly without flipping every page!

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 given name. Doing this by flipping pages one by one is slow and tiring.

The Problem

Searching manually means checking every name until you find the closest match. This takes a lot of time and you can easily miss the right spot or get confused, especially with many names.

The Solution

Using a Binary Search Tree (BST) with floor and ceil operations lets you quickly jump to the closest smaller or larger value without checking every item. It smartly moves left or right based on comparisons, saving time and effort.

Before vs After

✗ Before

for _, name := range phoneBook {
    if name <= target {
        floor = name
    }
    if name >= target && ceil == "" {
        ceil = name
    }
}

✓ After

func findFloor(node *Node, target int) int {
    if node == nil {
        return -1
    }
    if node.value == target {
        return node.value
    }
    if node.value > target {
        return findFloor(node.left, target)
    }
    floorValue := findFloor(node.right, target)
    if floorValue != -1 {
        return floorValue
    }
    return node.value
}

What It Enables

This lets you instantly find the closest smaller or larger value in sorted data, making searches lightning fast and accurate.

Real Life Example

When booking flights, you want to find the closest available departure time before or after your preferred time. Floor and ceil in BST help find these times quickly.

Key Takeaways

Manual search is slow and error-prone for closest values.

Floor and ceil in BST use smart moves to find closest smaller or larger values fast.

This makes searching in sorted data efficient and reliable.