Ceil in a Binary Search Tree Python

Binary Search Tree In Python

In a Binary Search Tree (BST), the ceiling of a given value is the smallest element in the tree that is greater than or equal to the given value. Finding the ceiling in a BST can be a useful operation when working with ordered data. In this article, we will explore how to find the ceiling in a Binary Search Tree using Python.

Binary Search Tree Overview

A Binary Search Tree is a binary tree data structure where each node has a key/value and follows a specific ordering property. The left child of a node contains a value smaller than the node’s value, while the right child contains a value greater than the node’s value. This ordering property allows for efficient searching, insertion, and deletion operations.

Finding the Ceiling in a Binary Search Tree

To find the ceiling in a Binary Search Tree, we can follow these steps:

Start at the root node of the BST.
If the root node’s value is equal to the given value, then the root node itself is the ceiling.
If the root node’s value is less than the given value, move to the right subtree recursively.
If the root node’s value is greater than the given value, move to the left subtree recursively.
Repeat steps 2-4 until we find the smallest value greater than or equal to the given value.

Example: Let’s consider the following Binary Search Tree:

          8
        /    \
      3       10
     / \         \
    1   6         14
       / \        /
      4   7    13

Suppose we want to find the ceiling of the value 5 in this BST. We can follow the steps mentioned earlier:

Start at the root node with a value of 8.
Since 8 is greater than 5, move to the left subtree.
Move to the left child with a value of 3.
Since 3 is less than 5, move to the right subtree.
Move to the right child with a value of 6.
Since 6 is greater than 5, move to the left subtree.
Move to the left child with a value of 4.
Since 4 is less than 5, move to the right subtree.
Move to the right child with a value of 7.
Since 7 is greater than 5, move to the left subtree.
There are no more left children, so the current node with a value of 7 is the ceiling of 5.

Therefore, the ceiling of 5 in this BST is 7.

Implementation of Ceil in a Binary Search Tree using Python

Here’s an example implementation of finding the ceiling in a Binary Search Tree using Python:

Python

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

def findCeiling(root, value):
    if root is None:
        return None

    if root.value == value:
        return root.value

    if root.value < value:
        return findCeiling(root.right, value)

    ceil = findCeiling(root.left, value)
    return ceil if ceil is not None and ceil >= value else root.value

# Create the Binary Search Tree
root = Node(8)
root.left = Node(3)
root.right = Node(10)
root.left.left = Node(1)
root.left.right = Node(6)
root.left.right.left = Node(4)
root.left.right.right = Node(7)
root.right.right = Node(14)
root.right.right.left = Node(13)

# Find the ceiling of 5
ceiling = findCeiling(root, 5)
print("Ceiling of 5:", ceiling)

Output

Ceiling of 5: 6

Conclusion

Finding the ceiling in a Binary Search Tree is a useful operation when working with ordered data. By following the steps outlined in this article and implementing the logic in Python, you can efficiently find the smallest element in a BST that is greater than or equal to a given value. Understanding this concept can be valuable in various scenarios, such as searching for the next highest value in a sorted collection of data.

Tags:

#Binary Tree #Python-DSA #Python #python