Floor and Ceil in BST 🎯

Welcome to our comprehensive guide on Floor and Ceil in Binary Search Trees (BST)! In this lesson, we'll explore these essential concepts, helping you navigate through real-world programming scenarios. Let's dive in!

What is a Binary Search Tree (BST)? 📝

A Binary Search Tree is a type of binary tree where the nodes are arranged in a specific order. Each node has at most two children, called the left child and the right child. In a BST, the left subtree's keys are always less than the parent node, while the right subtree's keys are greater than the parent node.

Understanding Floor and Ceil 💡

The Floor and Ceil functions in a BST help find the closest smaller and larger keys, respectively. They are particularly useful when you're looking for an element that's not present in the tree or when you need to perform operations like finding the successor or predecessor.

Floor in BST 📝

The Floor operation returns the largest key in the tree that is less than or equal to the given key. If the given key is less than the smallest key in the tree, the Floor operation returns null or None.

Ceil in BST 📝

The Ceil operation returns the smallest key in the tree that is greater than or equal to the given key. If the given key is greater than the largest key in the tree, the Ceil operation returns null or None.

Implementing Floor and Ceil in Python 💡

Let's create a simple BST and implement the Floor and Ceil functions using recursion.

python

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.key = key

class BST:
    def __init__(self):
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            self._insert(self.root, key)

    def _insert(self, node, key):
        if key < node.key:
            if node.left is None:
                node.left = Node(key)
            else:
                self._insert(node.left, key)
        elif key > node.key:
            if node.right is None:
                node.right = Node(key)
            else:
                self._insert(node.right, key)

    def floor(self, key):
        return self._floor(self.root, key).key

    def _floor(self, node, key):
        if node is None:
            return None

        if node.key < key:
            max_left = self._floor(node.right, key)
            if max_left is not None:
                return max_left

            return node.key

        return self._floor(node.left, key)

    def ceil(self, key):
        return self._ceil(self.root, key).key

    def _ceil(self, node, key):
        if node is None:
            return None

        if node.key > key:
            min_right = self._ceil(node.left, key)
            if min_right is not None:
                return min_right

            return node.key

        return self._ceil(node.right, key)

bst = BST()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)

print(f"Floor of 25: {bst.floor(25)}")
print(f"Ceil of 25: {bst.ceil(25)}")

In this example, we've created a BST with integers 50, 30, 20, 40, 70, 60, and 80. Running the above code will output:

Floor of 25: 20
Ceil of 25: 30

Now that you have a grasp of Floor and Ceil operations in BST, let's test your understanding!