Okay, let’s dive into implementing a Binary Search Tree (BST) in Python.
A Binary Search Tree is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys lesser than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. The left and right subtree each must also be a binary search tree. There must be no duplicate nodes. (Some implementations allow duplicates, but the standard definition usually implies unique keys or special handling for duplicates).
Core Components
A BST typically involves two classes:
Node Class: Represents a single node in the tree. Each node will usually have:
- key: The value stored in the node (used for comparisons). left: A reference to the left child node. right: A reference to the right child node.
BinarySearchTree Class: Manages the overall tree structure. It will typically have:
- root: A reference to the root node of the tree. Methods for common operations like insert, search, delete, and traversals.
Implementation in Python
Python
Class Node:
"""
Represents a single node in the Binary Search Tree.
"""
def __init__(self, key):
self. key = key
self. left = None
self. right = None
def __str__(self):
return str(self. key)
def __repr__(self):
return f"Node({self. key})"
Class BinarySearchTree:
"""
Implements a Binary Search Tree.
"""
def __init__(self):
self. root = None
def insert(self, key):
"""
Inserts a new key into the BST.
If the tree is empty, the new key becomes the root.
Otherwise, it recursively finds the correct position based on the key’s value.
Handles duplicates by doing nothing (or you could raise an error/update value).
"""
if self. root is None:
self. root = Node(key)
else:
self._insert_recursive(self. root, key)
def _insert_recursive(self, node, key):
"""Helper method for recursive insertion."""
if key < node. key:
if node. left is None:
node. left = Node(key)
else:
self._insert_recursive(node. left, key)
elif key > node. key: # Key must be greater than node. key for right subtree
if node. right is None:
node. right = Node(key)
else:
self._insert_recursive(node. right, key)
# If key == node. key, it’s a duplicate. We do nothing.
# You could add a print statement or raise an error here if desired.
else:
# print(f"Key {key} already exists in the tree.")
pass
def search(self, key):
"""
Searches for a key in the BST.
Returns the Node object if found, otherwise returns None.
"""
return self._search_recursive(self. root, key)
def _search_recursive(self, node, key):
"""Helper method for recursive search."""
if node is None:
return None
if key == node. key:
return node
elif key < node. key:
return self._search_recursive(node. left, key)
else: # key > node. key
return self._search_recursive(node. right, key)
def delete(self, key):
"""
Deletes a key from the BST.
Handles three cases:
1. Node to be deleted has no children.
2. Node to be deleted has one child.
3. Node to be deleted has two children.
"""
self. root = self._delete_recursive(self. root, key)
def _delete_recursive(self, node, key):
"""Helper method for recursive deletion."""
if node is None:
return node # Key not found
# 1. Traverse to find the node to be deleted
if key < node. key:
node. left = self._delete_recursive(node. left, key)
elif key > node. key:
node. right = self._delete_recursive(node. right, key)
else: # node. key == key, this is the node to be deleted
# Case 1: Node has no children or only one child
if node. left is None:
return node. right
elif node. right is None:
return node. left
# Case 3: Node has two children
# Find the in-order successor (smallest in the right subtree)
temp_node = self._find_min(node. right)
node. key = temp_node. key # Copy the in-order successor’s key to this node
node. right = self._delete_recursive(node. right, temp_node. key) # Delete the in-order successor
return node
def _find_min(self, node):
"""Helper method to find the node with the minimum key in a subtree."""
current = node
while current. left is not None:
current = current. left
return current
# — Tree Traversals (for printing/inspection) —
def inorder_traversal(self):
"""
Performs an in-order traversal (Left -> Root -> Right).
Returns a list of keys in ascending order.
"""
result = []
self._inorder_recursive(self. root, result)
return result
def _inorder_recursive(self, node, result):
if node:
self._inorder_recursive(node. left, result)
result. append(node. key)
self._inorder_recursive(node. right, result)
def preorder_traversal(self):
"""
Performs a pre-order traversal (Root -> Left -> Right).
"""
result = []
self._preorder_recursive(self. root, result)
return result
def _preorder_recursive(self, node, result):
if node:
result. append(node. key)
self._preorder_recursive(node. left, result)
self._preorder_recursive(node. right, result)
def postorder_traversal(self):
"""
Performs a post-order traversal (Left -> Right -> Root).
"""
result = []
self._postorder_recursive(self. root, result)
return result
def _postorder_recursive(self, node, result):
if node:
self._postorder_recursive(node. left, result)
self._postorder_recursive(node. right, result)
result. append(node. key)
def level_order_traversal(self):
"""
Performs a level-order (breadth-first) traversal.
Returns a list of lists, where each inner list represents a level.
"""
if not self. root:
return []
levels = []
queue = [(self. root, 0)] # (node, level)
while queue:
node, level = queue. pop(0) # Pop from the front for BFS
if len(levels) == level:
levels. append([])
levels[level].append(node. key)
if node. left:
queue. append((node. left, level + 1))
if node. right:
queue. append((node. right, level + 1))
return levels
# — Example Usage —
If __name__ == "__main__":
bst = BinarySearchTree()
keys = [50, 30, 70, 20, 40, 60, 80, 25, 35, 75, 85]
print("Inserting keys:", keys)
for key in keys:
bst. insert(key)
print("\n— Traversals —")
print("In-order traversal (sorted):", bst. inorder_traversal())
print("Pre-order traversal (root, left, right):", bst. preorder_traversal())
print("Post-order traversal (left, right, root):", bst. postorder_traversal())
print("Level-order traversal:")
for level_nodes in bst. level_order_traversal():
print(f" Level: {level_nodes}")
print("\n— Search Operations —")
key_to_find = 40
node = bst. search(key_to_find)
if node:
print(f"Key {key_to_find} found: {node. key}")
else:
print(f"Key {key_to_find} not found.")
key_to_find = 99
node = bst. search(key_to_find)
if node:
print(f"Key {key_to_find} found: {node. key}")
else:
print(f"Key {key_to_find} not found.")
print("\n— Deletion Operations —")
print("In-order before deletion:", bst. inorder_traversal())
print("Deleting 20 (no children)…")
bst. delete(20)
print("In-order after deleting 20:", bst. inorder_traversal()) # Should be [25, 30, 35, 40, 50, 60, 70, 75, 80, 85]
print("\nDeleting 70 (two children — replaced by in-order successor 75)…")
bst. delete(70)
print("In-order after deleting 70:", bst. inorder_traversal()) # Should be [25, 30, 35, 40, 50, 60, 75, 80, 85]
print("\nDeleting 30 (one child — 35)…")
bst. delete(30)
print("In-order after deleting 30:", bst. inorder_traversal()) # Should be [25, 35, 40, 50, 60, 75, 80, 85]
print("\nDeleting 50 (root node, two children — replaced by in-order successor 60)…")
bst. delete(50)
print("In-order after deleting 50:", bst. inorder_traversal()) # Should be [25, 35, 40, 60, 75, 80, 85]
print("\nAttempting to delete a non-existent key (99):")
bst. delete(99)
print("In-order after trying to delete 99:", bst. inorder_traversal()) # Should be unchanged
Explanation of Key Methods:
Insert(self, key)
- Recursive approach: It checks if the tree is empty. If so, the key becomes the root. Otherwise, it calls a private helper _insert_recursive. The helper compares key with the current node. key:
- If key < node. key, it tries to insert into the left subtree. If key > node. key, it tries to insert into the right subtree. If key == node. key, it’s a duplicate, and the current implementation ignores it.
Search(self, key)
- Also uses a recursive helper _search_recursive. It compares key with node. key:
- If key == node. key, the node is found. If key < node. key, search in the left subtree. If key > node. key, search in the right subtree.
If node becomes None (reached a leaf without finding the key), it means the key is not in the tree.
Delete(self, key)
This is the most complex operation in a BST, handling three cases:
Node has no children (Leaf Node): Simply remove the node by setting its parent’s pointer to None. Node has one child: Replace the node with its only child. The child takes its place. Node has two children:
- Find the In-order successor of the node to be deleted. The in-order successor is the smallest key in the right subtree (or the largest key in the left subtree, but the smallest in the right is more common). Copy the key of the in-order successor to the node being deleted. Recursively delete the in-order successor from the right subtree. This effectively moves the successor up to replace the deleted node, maintaining the BST properties.
The _find_min helper is used to find the in-order successor.
Traversal Methods (Inorder_traversal, Preorder_traversal, Postorder_traversal, Level_order_traversal)
These methods are crucial for visiting all nodes in a specific order:
- In-order (Left, Root, Right): Visits nodes in ascending order of their keys. Useful for getting sorted elements. Pre-order (Root, Left, Right): Visits the root first, then its left subtree, then its right subtree. Useful for copying a tree. Post-order (Left, Right, Root): Visits the left subtree, then the right, then the root. Useful for deleting a tree. Level-order (Breadth-First): Visits nodes level by level, from left to right. Implemented using a queue.
Time Complexity:
|
Operation |
Average Case |
Worst Case (Degenerate Tree) |
|
Insertion |
O(log N) |
O(N) |
|
Search |
O(log N) |
O(N) |
|
Deletion |
O(log N) |
O(N) |
|
Traversal (all) |
O(N) |
O(N) |
N is the number of nodes in the tree.
The "worst case" occurs when the tree is degenerate (e. g., all inserted elements are in strictly increasing or decreasing order), effectively becoming a linked list. To avoid this, Self-balancing BSTs like AVL trees or Red-Black trees are used in practice, which maintain a logarithmic height even in the worst case.
