Lecture 184:-  BST Class - 2

Certainly! Let's continue enhancing our Binary Search Tree (BST) class by adding more functionalities such as deletion, traversal methods, and checking whether the tree is balanced or not. Additionally, we'll add methods to perform in-order, pre-order, and post-order traversals.

Here's the continuation of the Binary Search Tree class:

pythonCopy code

class BinarySearchTree: def __init__(self): self.root = None def insert(self, data): self.root = self._insert_recursively(self.root, data) def _insert_recursively(self, node, data): if node is None: return TreeNode(data) if data < node.data: node.left = self._insert_recursively(node.left, data) elif data > node.data: node.right = self._insert_recursively(node.right, data) return node def search(self, data): return self._search_recursively(self.root, data) def _search_recursively(self, node, data): if node is None or node.data == data: return node if data < node.data: return self._search_recursively(node.left, data) else: return self._search_recursively(node.right, data) def delete(self, data): self.root = self._delete_recursively(self.root, data) def _delete_recursively(self, node, data): if node is None: return node if data < node.data: node.left = self._delete_recursively(node.left, data) elif data > node.data: node.right = self._delete_recursively(node.right, data) else: if node.left is None: return node.right elif node.right is None: return node.left min_right_subtree = self._find_min(node.right) node.data = min_right_subtree.data node.right = self._delete_recursively(node.right, min_right_subtree.data) return node def _find_min(self, node): while node.left: node = node.left return node def in_order_traversal(self): self._in_order_recursively(self.root) print() def _in_order_recursively(self, node): if node: self._in_order_recursively(node.left) print(node.data, end=" ") self._in_order_recursively(node.right) def pre_order_traversal(self): self._pre_order_recursively(self.root) print() def _pre_order_recursively(self, node): if node: print(node.data, end=" ") self._pre_order_recursively(node.left) self._pre_order_recursively(node.right) def post_order_traversal(self): self._post_order_recursively(self.root) print() def _post_order_recursively(self, node): if node: self._post_order_recursively(node.left) self._post_order_recursively(node.right) print(node.data, end=" ") def is_balanced(self): return self._is_balanced_recursively(self.root) is not None def _is_balanced_recursively(self, node): if node is None: return 0 left_height = self._is_balanced_recursively(node.left) right_height = self._is_balanced_recursively(node.right) if left_height is None or right_height is None: return None if abs(left_height - right_height) > 1: return None return max(left_height, right_height) + 1 # Example usage bst = BinarySearchTree() bst.insert(10) bst.insert(5) bst.insert(15) bst.insert(3) bst.insert(7) bst.insert(12) bst.insert(18) print("In-order traversal:") bst.in_order_traversal() print("Pre-order traversal:") bst.pre_order_traversal() print("Post-order traversal:") bst.post_order_traversal() delete_value = 10 bst.delete(delete_value) print(f"Deleted node with value {delete_value}") bst.in_order_traversal() print("Is the tree balanced?", bst.is_balanced())

In this continuation, we've added the following functionalities to the BinarySearchTree class:

Delete Node: The delete method allows you to delete a node with a given value from the tree. It maintains the binary search tree property while deleting nodes.

Traversal Methods: The in_order_traversal, pre_order_traversal, and post_order_traversal methods perform in-order, pre-order, and post-order traversals of the binary search tree, respectively.

Is Balanced: The is_balanced method checks whether the binary search tree is balanced or not. It uses a similar approach as before to calculate the heights of subtrees while checking for balance.

This enhanced Binary Search Tree class now includes more functionalities commonly associated with binary search trees. You can further expand it by adding other operations and algorithms related to binary search trees.