Binary Search Trees #
Welcome to Day 15 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive into Binary Search Trees (BST), a powerful data structure that combines the efficiency of binary search with the flexibility of a linked data structure.
What is a Binary Search Tree? #
A Binary Search Tree is a binary tree with the following properties:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
These properties make BSTs efficient for search, insertion, and deletion operations.
Implementing a Binary Search Tree in Python #
Let’s implement a basic Binary Search Tree:
class BSTNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, key):
self.root = self._insert_recursive(self.root, key)
def _insert_recursive(self, root, key):
if root is None:
return BSTNode(key)
if key < root.key:
root.left = self._insert_recursive(root.left, key)
else:
root.right = self._insert_recursive(root.right, key)
return root
def search(self, key):
return self._search_recursive(self.root, key)
def _search_recursive(self, root, key):
if root is None or root.key == key:
return root
if key < root.key:
return self._search_recursive(root.left, key)
return self._search_recursive(root.right, key)
def inorder_traversal(self):
self._inorder_recursive(self.root)
def _inorder_recursive(self, root):
if root:
self._inorder_recursive(root.left)
print(root.key, end=" ")
self._inorder_recursive(root.right)
# Example usage
bst = BinarySearchTree()
keys = [50, 30, 70, 20, 40, 60, 80]
for key in keys:
bst.insert(key)
print("Inorder traversal of the BST:")
bst.inorder_traversal()
BST Operations #
1. Insertion #
The insertion operation in a BST maintains the BST property:
- If the tree is empty, create a new node and set it as the root.
- Otherwise, compare the key with the root:
- If the key is less than the root, insert it into the left subtree.
- If the key is greater than the root, insert it into the right subtree.
- Repeat this process recursively until you find an empty spot.
Time Complexity: O(h), where h is the height of the tree. In a balanced BST, this is O(log n).
2. Search #
Searching in a BST is efficient due to its structure:
- Start at the root.
- If the key matches the current node, return the node.
- If the key is less than the current node, search in the left subtree.
- If the key is greater than the current node, search in the right subtree.
- Repeat until you find the key or reach a leaf node.
Time Complexity: O(h), where h is the height of the tree. In a balanced BST, this is O(log n).
3. Deletion #
Deleting a node from a BST is more complex and involves three cases:
- Node to be deleted is a leaf: Simply remove it.
- Node has one child: Replace the node with its child.
- Node has two children: Find the inorder successor (minimum value in the right subtree), replace the node’s value with the successor’s value, and delete the successor.
Let’s implement the deletion operation:
class BinarySearchTree:
# ... (previous methods remain the same)
def delete(self, key):
self.root = self._delete_recursive(self.root, key)
def _delete_recursive(self, root, key):
if root is None:
return root
if key < root.key:
root.left = self._delete_recursive(root.left, key)
elif key > root.key:
root.right = self._delete_recursive(root.right, key)
else:
# Node with only one child or no child
if root.left is None:
return root.right
elif root.right is None:
return root.left
# Node with two children
root.key = self._min_value(root.right)
root.right = self._delete_recursive(root.right, root.key)
return root
def _min_value(self, node):
current = node
while current.left is not None:
current = current.left
return current.key
# Example usage
bst = BinarySearchTree()
keys = [50, 30, 70, 20, 40, 60, 80]
for key in keys:
bst.insert(key)
print("Original BST:")
bst.inorder_traversal()
bst.delete(30)
print("\nBST after deleting 30:")
bst.inorder_traversal()
Time Complexity: O(h), where h is the height of the tree. In a balanced BST, this is O(log n).
Balancing Binary Search Trees #
The efficiency of BST operations depends on the height of the tree. In the worst case, when the tree becomes skewed (essentially a linked list), the time complexity degrades to O(n).
To maintain efficiency, we use self-balancing BSTs such as:
- AVL Trees
- Red-Black Trees
These structures automatically keep the tree balanced after insertions and deletions, ensuring O(log n) time complexity for basic operations.
Applications of Binary Search Trees #
- Implementing associative arrays (dictionaries)
- Database indexing
- Implementing priority queues
- Syntax trees in compilers
- Searching algorithms
Exercise #
- Implement a function to find the kth smallest element in a BST.
- Create a method to check if a binary tree is a valid BST.
- Implement a function to find the lowest common ancestor of two nodes in a BST.
Summary #
Binary Search Trees are powerful data structures that provide efficient searching, insertion, and deletion operations. They form the basis for more advanced self-balancing trees and are crucial in many applications requiring fast look-up, addition, and removal of ordered data.
Understanding BSTs is essential for tackling more complex tree-based problems and is often a prerequisite for advanced algorithms involving balanced trees and tree-based data structures.
Tomorrow, we’ll explore tree traversal techniques in more depth, including both recursive and iterative approaches. Stay tuned!