Binary Search Trees
Master efficient searching and sorting with BSTs
🔍 What are Binary Search Trees?
Binary Search Trees (BST) are binary trees with a special ordering property: for every node, all values in the left subtree are smaller, and all values in the right subtree are larger. This enables efficient searching, insertion, and deletion operations.
# BST Node structure
class BSTNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# BST property: left < root < right
# 8
# / \
# 3 10
# / \ \
# 1 6 14
O(log n)
Average Search
Ordered
In-order
Dynamic
Insert/Delete
BST Properties
Ordering Property
Left < Root < Right for all nodes
Sorted structure
Efficient search
Fast Operations
O(log n) average time complexity
Search
Insert/Delete
In-order Traversal
Gives sorted sequence
Ascending order
Range queries
Dynamic Structure
Supports insertions and deletions
Flexible size
Real-time updates
Lesson 1: Implementing a Binary Search Tree
Let's build a complete BST with all essential operations:
BST Example
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
BST Implementation
class BSTNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, data):
"""Insert a new value into the BST"""
self.root = self._insert_recursive(self.root, data)
def _insert_recursive(self, node, data):
"""Helper method for recursive insertion"""
# Base case: create new node
if node is None:
return BSTNode(data)
# Insert in left subtree if data is smaller
if data < node.data:
node.left = self._insert_recursive(node.left, data)
# Insert in right subtree if data is larger
elif data > node.data:
node.right = self._insert_recursive(node.right, data)
# If data already exists, don't insert duplicate
return node
def search(self, data):
"""Search for a value in the BST"""
return self._search_recursive(self.root, data)
def _search_recursive(self, node, data):
"""Helper method for recursive search"""
# Base case: not found or found
if node is None or node.data == data:
return node
# Search in left subtree if data is smaller
if data < node.data:
return self._search_recursive(node.left, data)
# Search in right subtree if data is larger
else:
return self._search_recursive(node.right, data)
def inorder_traversal(self):
"""Get sorted list of all values"""
result = []
self._inorder_recursive(self.root, result)
return result
def _inorder_recursive(self, node, result):
"""Helper method for in-order traversal"""
if node:
self._inorder_recursive(node.left, result)
result.append(node.data)
self._inorder_recursive(node.right, result)
# Create and test BST
bst = BinarySearchTree()
values = [8, 3, 10, 1, 6, 14, 4, 7, 13]
print("Inserting values:", values)
for value in values:
bst.insert(value)
print("In-order traversal (sorted):", bst.inorder_traversal())
# Test search
search_values = [6, 15, 1, 12]
for val in search_values:
found = bst.search(val)
print(f"Search {val}: {'Found' if found else 'Not found'}")
Lesson 2: Deleting Nodes from BST
Deletion is the most complex BST operation with three cases to handle:
BST Deletion Implementation
🔹Complete deletion implementation
def delete(self, data):
"""Delete a value from the BST"""
self.root = self._delete_recursive(self.root, data)
def _delete_recursive(self, node, data):
"""Helper method for recursive deletion"""
# Base case: node not found
if node is None:
return node
# Find the node to delete
if data < node.data:
node.left = self._delete_recursive(node.left, data)
elif data > node.data:
node.right = self._delete_recursive(node.right, data)
else:
# Node to delete found - handle three cases
# Case 1: Node has no children (leaf node)
if node.left is None and node.right is None:
return None
# Case 2: Node has one child
elif node.left is None:
return node.right
elif node.right is None:
return node.left
# Case 3: Node has two children
else:
# Find inorder successor (smallest in right subtree)
successor = self._find_min(node.right)
# Replace node's data with successor's data
node.data = successor.data
# Delete the successor
node.right = self._delete_recursive(node.right, successor.data)
return node
def _find_min(self, node):
"""Find the minimum value node in a subtree"""
while node.left is not None:
node = node.left
return node
def _find_max(self, node):
"""Find the maximum value node in a subtree"""
while node.right is not None:
node = node.right
return node
# Add these methods to the BinarySearchTree class
BinarySearchTree.delete = delete
BinarySearchTree._delete_recursive = _delete_recursive
BinarySearchTree._find_min = _find_min
BinarySearchTree._find_max = _find_max
# Test deletion
print("\nTesting deletion:")
print("Before deletion:", bst.inorder_traversal())
# Delete leaf node
bst.delete(4)
print("After deleting 4 (leaf):", bst.inorder_traversal())
# Delete node with one child
bst.delete(14)
print("After deleting 14 (one child):", bst.inorder_traversal())
# Delete node with two children
bst.delete(3)
print("After deleting 3 (two children):", bst.inorder_traversal())
🔹Deletion cases visualization
def print_deletion_cases():
"""Demonstrate the three deletion cases"""
print("BST Deletion Cases:")
print("=" * 50)
print("\nCase 1: Delete leaf node (no children)")
print("Before: 8 → 3 → 1 (delete 1)")
print("After: 8 → 3")
print("\nCase 2: Delete node with one child")
print("Before: 8 → 10 → 14 (delete 10)")
print("After: 8 → 14")
print("\nCase 3: Delete node with two children")
print("Before: 8 → 3(1,6) (delete 3)")
print("Step 1: Find successor (4)")
print("Step 2: Replace 3 with 4")
print("Step 3: Delete original 4")
print("After: 8 → 4(1,6)")
print_deletion_cases()
Lesson 3: Advanced BST Operations
Let's implement more sophisticated BST operations:
Advanced BST Operations
🔹Find minimum and maximum values
def find_min_value(self):
"""Find the minimum value in the BST"""
if self.root is None:
return None
return self._find_min(self.root).data
def find_max_value(self):
"""Find the maximum value in the BST"""
if self.root is None:
return None
return self._find_max(self.root).data
# Add to BST class
BinarySearchTree.find_min_value = find_min_value
BinarySearchTree.find_max_value = find_max_value
print(f"Minimum value: {bst.find_min_value()}")
print(f"Maximum value: {bst.find_max_value()}")
🔹Find predecessor and successor
def find_predecessor(self, data):
"""Find the predecessor (largest smaller value)"""
predecessor = None
current = self.root
while current:
if data > current.data:
predecessor = current.data
current = current.right
else:
current = current.left
return predecessor
def find_successor(self, data):
"""Find the successor (smallest larger value)"""
successor = None
current = self.root
while current:
if data < current.data:
successor = current.data
current = current.left
else:
current = current.right
return successor
# Add to BST class
BinarySearchTree.find_predecessor = find_predecessor
BinarySearchTree.find_successor = find_successor
# Test predecessor and successor
test_value = 6
print(f"Predecessor of {test_value}: {bst.find_predecessor(test_value)}")
print(f"Successor of {test_value}: {bst.find_successor(test_value)}")
🔹Range queries
def range_query(self, min_val, max_val):
"""Find all values in the given range [min_val, max_val]"""
result = []
self._range_query_recursive(self.root, min_val, max_val, result)
return result
def _range_query_recursive(self, node, min_val, max_val, result):
"""Helper method for range query"""
if node is None:
return
# If current node is in range, add it
if min_val <= node.data <= max_val:
result.append(node.data)
# Recursively search left subtree if needed
if node.data > min_val:
self._range_query_recursive(node.left, min_val, max_val, result)
# Recursively search right subtree if needed
if node.data < max_val:
self._range_query_recursive(node.right, min_val, max_val, result)
# Add to BST class
BinarySearchTree.range_query = range_query
BinarySearchTree._range_query_recursive = _range_query_recursive
# Test range query
range_result = bst.range_query(5, 12)
print(f"Values between 5 and 12: {range_result}")
🔹Validate BST property
def is_valid_bst(self):
"""Check if the tree maintains BST property"""
return self._is_valid_bst_recursive(self.root, float('-inf'), float('inf'))
def _is_valid_bst_recursive(self, node, min_val, max_val):
"""Helper method to validate BST property"""
if node is None:
return True
# Check if current node violates BST property
if node.data <= min_val or node.data >= max_val:
return False
# Recursively validate left and right subtrees
return (self._is_valid_bst_recursive(node.left, min_val, node.data) and
self._is_valid_bst_recursive(node.right, node.data, max_val))
# Add to BST class
BinarySearchTree.is_valid_bst = is_valid_bst
BinarySearchTree._is_valid_bst_recursive = _is_valid_bst_recursive
print(f"Is valid BST: {bst.is_valid_bst()}")
Lesson 4: BST Performance and Balance
Understanding BST performance characteristics and balance issues:
BST Performance Analysis
🔹Calculate tree height and balance
def height(self):
"""Calculate the height of the BST"""
return self._height_recursive(self.root)
def _height_recursive(self, node):
"""Helper method to calculate height"""
if node is None:
return -1
left_height = self._height_recursive(node.left)
right_height = self._height_recursive(node.right)
return max(left_height, right_height) + 1
def is_balanced(self):
"""Check if the BST is height-balanced"""
def check_balance(node):
if node is None:
return 0, True
left_height, left_balanced = check_balance(node.left)
right_height, right_balanced = check_balance(node.right)
height_diff = abs(left_height - right_height)
current_balanced = (height_diff <= 1 and
left_balanced and right_balanced)
return max(left_height, right_height) + 1, current_balanced
_, balanced = check_balance(self.root)
return balanced
# Add to BST class
BinarySearchTree.height = height
BinarySearchTree._height_recursive = _height_recursive
BinarySearchTree.is_balanced = is_balanced
print(f"Tree height: {bst.height()}")
print(f"Is balanced: {bst.is_balanced()}")
🔹Demonstrate skewed vs balanced BST
def demonstrate_balance():
"""Show the difference between balanced and skewed BSTs"""
print("\nBalanced BST vs Skewed BST:")
print("=" * 50)
# Create balanced BST
balanced_bst = BinarySearchTree()
balanced_values = [4, 2, 6, 1, 3, 5, 7]
for val in balanced_values:
balanced_bst.insert(val)
# Create skewed BST (worst case)
skewed_bst = BinarySearchTree()
skewed_values = [1, 2, 3, 4, 5, 6, 7]
for val in skewed_values:
skewed_bst.insert(val)
print(f"Balanced BST:")
print(f" Values: {balanced_values}")
print(f" Height: {balanced_bst.height()}")
print(f" Is balanced: {balanced_bst.is_balanced()}")
print(f"\nSkewed BST:")
print(f" Values: {skewed_values}")
print(f" Height: {skewed_bst.height()}")
print(f" Is balanced: {skewed_bst.is_balanced()}")
print(f"\nPerformance Impact:")
print(f" Balanced: O(log n) = O(log 7) ≈ 3 operations")
print(f" Skewed: O(n) = O(7) = 7 operations")
demonstrate_balance()
Real-World Applications
Database Indexing
- B-tree variants
- Fast record lookup
- Range queries
- Sorted data retrieval
Expression Parsing
- Operator precedence
- Syntax trees
- Compiler design
- Mathematical expressions
File Systems
- Directory structures
- File organization
- Quick file lookup
- Hierarchical storage
Priority Systems
- Task scheduling
- Event management
- Resource allocation
- Queue management