# ================================
# Program: Binary Search Tree (BST)
# ================================
from collections import deque
# --------- NODE DEFINITION ---------
class Node:
def __init__(self, key):
[Link] = key
[Link] = None
[Link] = None
# --------- BST IMPLEMENTATION ---------
class BST:
def __init__(self):
[Link] = None
# a) INSERT NODE (handle duplicates)
def insert(self, key):
def _insert(root, key):
if root is None:
return Node(key)
if key < [Link]:
[Link] = _insert([Link], key)
elif key > [Link]:
[Link] = _insert([Link], key)
else:
print(f"⚠️Duplicate entry '{key}' not inserted.")
return root
[Link] = _insert([Link], key)
# b) DELETE NODE
def delete(self, key):
def _min_value_node(node):
current = node
while [Link]:
current = [Link]
return current
def _delete(root, key):
if not root:
print(f"❌ Key {key} not found.")
return root
if key < [Link]:
[Link] = _delete([Link], key)
elif key > [Link]:
[Link] = _delete([Link], key)
else:
# Node found
if not [Link]:
return [Link]
elif not [Link]:
return [Link]
temp = _min_value_node([Link])
[Link] = [Link]
[Link] = _delete([Link], [Link])
return root
[Link] = _delete([Link], key)
# c) DISPLAY PARENTS WITH THEIR CHILDREN
def display_parents(self, node):
if node:
if [Link] or [Link]:
print(f"Parent Node: {[Link]}")
if [Link]:
print(f" ├── Left Child: {[Link]}")
else:
print(" ├── Left Child: None")
if [Link]:
print(f" └── Right Child: {[Link]}")
else:
print(" └── Right Child: None")
self.display_parents([Link])
self.display_parents([Link])
# d) DISPLAY LEAF NODES
def display_leaf_nodes(self, node):
if node:
if [Link] is None and [Link] is None:
print(f"Leaf Node: {[Link]}")
self.display_leaf_nodes([Link])
self.display_leaf_nodes([Link])
# e) DISPLAY LEVEL-WISE (BFS Traversal)
def display_level_wise(self):
if [Link] is None:
print("🌳 Tree is empty.")
return
print("\nLevel-wise Display:")
q = deque()
[Link]([Link])
level = 1
while q:
n = len(q)
print(f"Level {level}: ", end="")
for i in range(n):
node = [Link]()
print([Link], end=" ")
if [Link]:
[Link]([Link])
if [Link]:
[Link]([Link])
print()
level += 1
# Utility function for inorder display
def inorder(self, node):
if node:
[Link]([Link])
print([Link], end=" ")
[Link]([Link])
def display_inorder(self):
if [Link] is None:
print("🌲 Tree is empty.")
else:
print("\nInorder Traversal: ", end="")
[Link]([Link])
print()
# --------- MAIN PROGRAM ---------
if __name__ == "__main__":
bst = BST()
while True:
print("\n===============================")
print(" BINARY SEARCH TREE MENU ")
print("===============================")
print("1. Insert Node")
print("2. Delete Node")
print("3. Display Parent and Child Nodes")
print("4. Display Leaf Nodes")
print("5. Display Tree Level-wise")
print("6. Display Inorder Traversal")
print("7. Exit")
choice = int(input("Enter your choice: "))
if choice == 1:
val = int(input("Enter value to insert: "))
[Link](val)
print("✅ Node inserted successfully!")
elif choice == 2:
val = int(input("Enter value to delete: "))
[Link](val)
elif choice == 3:
if [Link] is None:
print("🌳 Tree is empty.")
else:
print("\nParent and Child Nodes:")
bst.display_parents([Link])
elif choice == 4:
if [Link] is None:
print("🌳 Tree is empty.")
else:
print("\nLeaf Nodes in the Tree:")
bst.display_leaf_nodes([Link])
elif choice == 5:
bst.display_level_wise()
elif choice == 6:
bst.display_inorder()
elif choice == 7:
print("\n👋 Exiting program. Goodbye!")
break
else:
print("\n⚠️Invalid choice. Please try again.")
