Lecture 183:- BST Class - 1

Certainly! Let's start by implementing a basic Binary Search Tree (BST) class in Python. A Binary Search Tree is a special type of binary tree where the value of each node is greater than or equal to the values of all the nodes in its left subtree and less than or equal to the values of all the nodes in its right subtree.

Here's a simple implementation of a Binary Search Tree class with insertion and search functionalities:

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 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) # 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) search_value = 7 result_node = bst.search(search_value) if result_node: print(f"Node with value {search_value} found in the BST.") else: print(f"Node with value {search_value} not found in the BST.")

In this implementation, we've defined a TreeNode class to represent nodes in the binary search tree. The BinarySearchTree class contains methods for inserting values into the tree and searching for a value in the tree.

The insert method uses a recursive approach to insert values into the binary search tree while maintaining the BST property. The search method also uses recursion to search for a value in the tree.

You can further enhance this implementation by adding more functionalities like deletion, traversal methods (in-order, pre-order, post-order), and checking whether the tree is balanced or not.