Python Program for BST Operations
This program implements three fundamental operations on a Binary Search Tree (BST): inserting a new node, deleting an existing node, and searching for a node. Each function is documented to explain its purpose and the approach used.
class TreeNode:
"""A node in a binary search tree."""
def __init__(self, key):
"""
Initialize a tree node with a key.
:param key: int, the integer key of the node
"""
self.left = None
self.right = None
self.val = key
class BinarySearchTree:
"""Operations on a binary search tree."""
def __init__(self):
"""Initialize an empty BST."""
self.root = None
def insert(self, key):
"""
Insert a new node with the given key in the BST.
:param key: int, the key to insert
"""
self.root = self._insert_recursive(self.root, key)
def _insert_recursive(self, node, key):
"""
Helper method to insert recursively based on BST properties.
:param node: TreeNode, the current node in the traversal
:param key: int, the key to insert
:return: TreeNode, the adjusted node
"""
if not node:
return TreeNode(key)
elif key < node.val:
node.left = self._insert_recursive(node.left, key)
else:
node.right = self._insert_recursive(node.right, key)
return node
def delete(self, key):
"""
Delete the node with the specified key from the BST.
:param key: int, the key of the node to delete
"""
self.root = self._delete_recursive(self.root, key)
def _delete_recursive(self, node, key):
"""
Helper method to delete a node recursively.
:param node: TreeNode, the current node in the traversal
:param key: int, the key of the node to delete
:return: TreeNode, the adjusted node after deletion
"""
if not node:
return node
if key < node.val: node.left = self._delete_recursive(node.left, key) elif key > node.val:
node.right = self._delete_recursive(node.right, key)
else:
if not node.left:
return node.right
elif not node.right:
return node.left
temp_val = self._get_min(node.right)
node.val = temp_val
node.right = self._delete_recursive(node.right, temp_val)
return node
def _get_min(self, node):
"""
Get the minimum value in the BST.
:param node: TreeNode, the node from where to find the minimum
:return: int, the minimum value found
"""
current = node
while current.left is not None:
current = current.left
return current.val
def search(self, key):
"""
Search for a node with the specified key in the BST.
:param key: int, the key to search for
:return: bool, True if the node is found, False otherwise
"""
return self._search_recursive(self.root, key)
def _search_recursive(self, node, key):
"""
Helper method to search for a key recursively.
:param node: TreeNode, the current node in the traversal
:param key: int, the key to search for
:return: bool, True if found, False otherwise
"""
if not node:
return False
elif key == node.val:
return True
elif key < node.val:
return self._search_recursive(node.left, key)
else:
return self._search_recursive(node.right, key)
# Example Usage
if __name__ == "__main__":
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)
print("Search for 40:", bst.search(40))
bst.delete(70)
print("Search for 70:", bst.search(70))
The program defines a TreeNode class to represent individual nodes of the BST and a BinarySearchTree class that encapsulates the operations. Each method in the BinarySearchTree class is accompanied by a helper function to facilitate recursive operations, ensuring that the tree’s properties are maintained throughout insertions, deletions, and searches.
