# Binary Search Tree implementation with user interaction
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
# Insert a node
def insert(self, key):
self.root = self._insert_recursive(self.root, key)
def _insert_recursive(self, root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = self._insert_recursive(root.left, key)
elif key > root.key:
root.right = self._insert_recursive(root.right, key)
return root
# Search a node
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)
# Delete a node
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 one 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:
current = current.left
return current.key
# Inorder traversal
def inorder(self):
self._inorder_recursive(self.root)
print()
def _inorder_recursive(self, root):
if root:
self._inorder_recursive(root.left)
print(root.key, end=" ")
self._inorder_recursive(root.right)
# Main program (User-driven)
bst = BinarySearchTree()
while True:
print("\n--- Binary Search Tree Menu ---")
print("1. Insert element")
print("2. Search element")
print("3. Delete element")
print("4. Display (Inorder Traversal)")
print("5. Exit")
choice = int(input("Enter your choice: "))
if choice == 1:
value = int(input("Enter value to insert: "))
bst.insert(value)
print("Inserted successfully.")
elif choice == 2:
value = int(input("Enter value to search: "))
result = bst.search(value)
if result:
print("Element found.")
else:
print("Element not found.")
elif choice == 3:
value = int(input("Enter value to delete: "))
bst.delete(value)
print("Deleted successfully (if existed).")
elif choice == 4:
print("BST Inorder Traversal:")
bst.inorder()
elif choice == 5:
print("Exiting program.")
break
else:
print("Invalid choice. Try again.")
Comments
Post a Comment