Binary Search Tree

A Binary Search Tree (BST) is a binary tree in which every node satisfies the following property: all values in the left subtree are smaller, and all values in the right subtree are larger, than the current node's value.

BST Property

       8
      / \
     3   10
    / \    \
   1   6    14

• Left of 8: all values < 8
• Right of 8: all values > 8
• This applies recursively to every subtree

Implementation

class BSTNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

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

    def insert(self, val):
        self.root = self._insert(self.root, val)

    def _insert(self, node, val):
        if not node:
            return BSTNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return node

    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if not node:
            return False
        if val == node.val:
            return True
        elif val < node.val:
            return self._search(node.left, val)
        else:
            return self._search(node.right, val)

Delete

    def delete(self, val):
        self.root = self._delete(self.root, val)

    def _delete(self, node, val):
        if not node:
            return None
        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:
            if not node.left:
                return node.right
            if not node.right:
                return node.left
            successor = self._min_node(node.right)
            node.val = successor.val
            node.right = self._delete(node.right, successor.val)
        return node

    def _min_node(self, node):
        while node.left:
            node = node.left
        return node

    def inorder(self):
        result = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.val)
            self._inorder(node.right, result)

Time Complexity

The Problem with a Plain BST

A BST can become skewed (like a linked list) if data arrives in sorted order:

# Sorted input: 1, 2, 3, 4, 5
# The BST becomes:
# 1
#  \
#   2
#    \
#     3
#      \
#       4
#        \
#         5
# Height = 5, search O(n)

A plain BST can lose its efficiency. The solution: a balanced tree such as the AVL Tree.