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:
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
Ceil in a Binary Search Tree 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.
Contact Us