BInary Search Tree (BST). Assignment

Assignment Implementing a Binary Search Tree (BST) Instructions: 1. Implement a Binary Search Tree (BST) in the programming language of your choice (e.g., C, C++, Java, Python). 2. Include functions/methods for insertion, deletion, and searching within the BST. 3. Test your implementation with a set of sample data to demonstrate the correctness of your code. 4. Provide comments and explanations for key parts of your code. 5. Discuss the time complexity of your implementation, particularly focusing on insertion, deletion, and searching operations. My code in Python: class Node: def __init__(self, key): self.key = key self.left = None self.right = None class BST: def __init__(self): self.root = None def insert(self, key): """Insert a key into the BST.""" self.root = self._insert(self.root, key) def _insert(self, root, key): """Helper function for insertion.""" if root is None: return Node(key) if key < root.key: root.left = self._insert(root.left, key) elif key > root.key: root.right = self._insert(root.right, key) return root def delete(self, key): """Delete a key from the BST.""" self.root = self._delete(self.root, key) def _delete(self, root, key): """Helper function for deletion.""" if root is None: return root if key < root.key: root.left = self._delete(root.left, key) elif key > root.key: root.right = self._delete(root.right, key) else: # Node with only one child 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._get_min_value(root.right) root.right = self._delete(root.right, root.key) return root def _get_min_value(self, root): """Helper function to find the minimum value in a subtree.""" while root.left is not None: root = root.left return root.key def search(self, key): """Search for a key in the BST.""" return self._search(self.root, key) def _search(self, root, key): """Helper function for searching.""" if root is None or root.key == key: return root if key < root.key: return self._search(root.left, key) elif key > root.key: return self._search(root.right, key) def inorder_traversal(self, root): """Perform an inorder traversal of the BST.""" if root is not None: self.inorder_traversal(root.left) print(root.key, end=" ") self.inorder_traversal(root.right) # Sample usage and testing bst = BST() data_to_insert = [50, 30, 70, 20, 40] for key in data_to_insert: bst.insert(key) print("Inorder Traversal:") bst.inorder_traversal(bst.root) print("\n") # Test deletion bst.delete(30) print("After deleting 30:") bst.inorder_traversal(bst.root) print("\n") explanation: The code defines a Node class to represent individual nodes in the BST. • The BST class has methods for insertion, deletion, searching, and an additional method for inorder traversal. • The insert, delete, and search methods are recursive and perform their respective operations. • The inorder_traversal method prints the nodes of the BST in ascending order. Time Complexity: The time complexity of insertion, deletion, and searching in the average case is O(log n), where n is the number of nodes in the tree. • However, in the worst case (e.g., unbalanced tree), the time complexity can be O(n) for insertion and deletion. Run Proof on terminal: