Lecture 173:- Trees Class - 3

Certainly, let's continue exploring more advanced features of a tree class. In this example, we'll implement a Binary Search Tree (BST) class with additional functionalities like searching for a value, finding the height of the tree, and deleting a node.

pythonCopy code

class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None 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: return False if data == node.data: return True elif data < node.data: return self._search_recursively(node.left, data) else: return self._search_recursively(node.right, data) def find_height(self): return self._find_height_recursively(self.root) def _find_height_recursively(self, node): if node is None: return -1 left_height = self._find_height_recursively(node.left) right_height = self._find_height_recursively(node.right) return max(left_height, right_height) + 1 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 # 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("Search for value 12:", bst.search(12)) print("Search for value 8:", bst.search(8)) print("Height of the tree:", bst.find_height()) print("In-order traversal after insertion:") bst.in_order_traversal(bst.root) print() bst.delete(10) print("In-order traversal after deletion:") bst.in_order_traversal(bst.root)

In this example, we've extended the BinarySearchTree class to include methods for searching, finding the height, and deleting nodes. The _search_recursively method searches for a value in the tree, while _find_height_recursively calculates the height of the tree using recursion. The _delete_recursively method handles the deletion of a node while maintaining the binary search tree property.

The delete method uses the _find_min method to find the minimum value in the right subtree when deleting a node with two children. This helps maintain the binary search tree structure.

This example showcases a more advanced implementation of a Binary Search Tree class, which includes common operations such as searching, finding the height, and deleting nodes. Binary Search Trees are a key concept in computer science and offer efficient searching and sorting capabilities.