DSA — Binary Search Trees

What is a BST?

A binary tree where left child < parent < right child.

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

Insert Operation

def insert(self, data):
    if not self.root:
        self.root = TreeNode(data)
    else:
        self._insert_recursive(self.root, data)

def _insert_recursive(self, node, data):
    if data < node.data:
        if node.left is None:
            node.left = TreeNode(data)
        else:
            self._insert_recursive(node.left, data)
    else:
        if node.right is None:
            node.right = TreeNode(data)
        else:
            self._insert_recursive(node.right, data)

Search Operation

def search(self, data):
    return self._search_recursive(self.root, data)

def _search_recursive(self, node, data):
    if node is None or node.data == data:
        return node
    if data < node.data:
        return self._search_recursive(node.left, data)
    return self._search_recursive(node.right, data)

Delete Operation

def delete(self, data):
    self.root = self._delete_recursive(self.root, data)

def _delete_recursive(self, node, data):
    if node is None:
        return node
    if data < node.data:
        node.left = self._delete_recursive(node.left, data)
    elif data > node.data:
        node.right = self._delete_recursive(node.right, data)
    else:
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        min_node = self._find_min(node.right)
        node.data = min_node.data
        node.right = self._delete_recursive(node.right, min_node.data)
    return node

Mini Practice

1. Implement a BST
2. Insert and search
3. Delete a node
4. Find min and max

Up Next

Continue with AVL Trees — self-balancing BST.