PYTHON
Simple Binary Search Tree (BST) Implementation in Python
Learn to build a Binary Search Tree in Python, an ordered data structure for efficient data retrieval, insertion, and deletion, crucial for optimized searching.
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, key):
self.root = self._insert_recursive(self.root, key)
def _insert_recursive(self, node, key):
if node is None:
return TreeNode(key)
if key < node.key:
node.left = self._insert_recursive(node.left, key)
elif key > node.key:
node.right = self._insert_recursive(node.right, key)
return node
def search(self, key):
return self._search_recursive(self.root, key)
def _search_recursive(self, node, key):
if node is None or node.key == key:
return node
if key < node.key:
return self._search_recursive(node.left, key)
return self._search_recursive(node.right, key)
def inorder_traversal(self):
elements = []
self._inorder_recursive(self.root, elements)
return elements
def _inorder_recursive(self, node, elements):
if node:
self._inorder_recursive(node.left, elements)
elements.append(node.key)
self._inorder_recursive(node.right, elements)
# Example Usage
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
bst.insert(60)
bst.insert(80)
print(f"Inorder Traversal: {bst.inorder_traversal()}")
print(f"Search for 40: {bst.search(40).key if bst.search(40) else 'Not Found'}")
print(f"Search for 90: {'Found' if bst.search(90) else 'Not Found'}")
How it works: This snippet implements a basic Binary Search Tree (BST) using Python classes. Each `TreeNode` stores a `key` and references to its `left` and `right` children. The `BinarySearchTree` class manages the `root` node. The `insert` method adds new keys while maintaining the BST property (left child < parent < right child), and the `search` method efficiently finds keys. `inorder_traversal` demonstrates visiting nodes in sorted order.