Minimum and Maximum in Binary Search Trees (BST)

Welcome to this comprehensive guide on finding the Minimum and Maximum values in Binary Search Trees (BST)! 🎯

Binary Search Trees are a type of tree data structure in computer science where each node has at most two children - a left child and a right child. They are a useful data structure for efficient search, insert, and delete operations. Today, we will focus on finding the minimum and maximum values in a Binary Search Tree.

Understanding Minimum and Maximum Values in BST

The minimum value in a BST is the smallest value, while the maximum value is the largest value. In a BST, the minimum value is always in the root node's left subtree, and the maximum value is always in the root node's right subtree.

💡 Pro Tip: In a BST, the left subtree of any node contains only nodes with keys less than the parent node, while the right subtree contains only nodes with keys greater than the parent node.

Finding Minimum and Maximum Values in BST

To find the minimum and maximum values, we will write two functions: findMin() and findMax(). Let's start with findMin().

python

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

def findMin(node):
    current = node
    while current.left is not None:
        current = current.left
    return current.val

# Example usage:
root = Node(10)
root.left = Node(2)
root.right = Node(15)
root.left.left = Node(1)
root.left.right = Node(4)

print("Minimum value in the BST: ", findMin(root.left.left))  # Output: 1

In this example, we start at the root node and traverse the left subtree until we reach the leftmost node, which is the minimum value.

The findMax() function is similar, but we traverse the right subtree instead:

python

def findMax(node):
    current = node
    while current.right is not None:
        current = current.right
    return current.val

# Example usage:
print("Maximum value in the BST: ", findMax(root.right))  # Output: 15

Now that you understand how to find the minimum and maximum values in a Binary Search Tree, let's test your knowledge with a quiz! 📝

That's it for today! You now know how to find the minimum and maximum values in a Binary Search Tree. Stay tuned for more lessons on data structures and algorithms at CodeYourCraft! 🚀

Don't forget to practice and experiment with the code examples provided. Happy coding! 💡