Data Structures

Binary Search Trees

● Intermediate ⏱ 10 min read trees

A Binary Search Tree (BST) is a binary tree with one crucial ordering constraint: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This ordering enables O(log n) search, insert, and delete on a balanced tree.

BST Property

Text

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

For node 8:
  left subtree  values {1,3,4,6,7}  — all < 8  ✓
  right subtree values {10,13,14}   — all > 8  ✓
This must hold for every node in the tree.

Python

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

    def __init__(self):
        self.root = None

Insertion

Walk the tree comparing values until reaching an empty spot, then attach the new node.

Python

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

def _insert(self, node, val):
    if node is None:
        return self.Node(val)
    if val < node.val:
        node.left  = self._insert(node.left, val)
    elif val > node.val:
        node.right = self._insert(node.right, val)
    # equal: duplicate — ignore (or update depending on design)
    return node

# Build the example tree
bst = BST()
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    bst.insert(v)

Search

At each node, compare the target with the node’s value and go left (smaller) or right (larger). Each step eliminates half the remaining tree on a balanced BST.

Python

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

def _search(self, node, val):
    if node is None:
        return False
    if val == node.val:
        return True
    if val < node.val:
        return self._search(node.left, val)
    return self._search(node.right, val)

# Iterative version — avoids recursion depth limit on large trees
def search_iter(self, val):
    node = self.root
    while node:
        if val == node.val:
            return True
        node = node.left if val < node.val else node.right
    return False

Deletion

BST deletion has three cases based on the number of children the target node has.

Python

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

def _delete(self, node, val):
    if node is None:
        return None                    # not found

    if val < node.val:
        node.left  = self._delete(node.left, val)
    elif val > node.val:
        node.right = self._delete(node.right, val)
    else:
        # Case 1: leaf — just remove it
        if not node.left and not node.right:
            return None

        # Case 2: one child — replace node with that child
        if not node.left:
            return node.right
        if not node.right:
            return node.left

        # Case 3: two children — replace with in-order successor
        # (smallest value in right subtree)
        successor = node.right
        while successor.left:
            successor = successor.left
        node.val   = successor.val              # copy successor value up
        node.right = self._delete(node.right, successor.val)  # delete successor

    return node

💡

Why the in-order successor?

The in-order successor is the smallest value larger than the deleted node. Replacing the node with it preserves the BST property: it is larger than the entire left subtree and smaller than all remaining right subtree values.

Degenerate BST

Inserting already-sorted data creates a degenerate (skewed) tree that is effectively a linked list: every node has only a right child. All operations degrade from O(log n) to O(n).

Python

# Inserting sorted data creates a degenerate tree
bst2 = BST()
for v in [1, 2, 3, 4, 5]:
    bst2.insert(v)

# Tree shape:
# 1
#  \
#   2
#    \
#     3
#      \
#       4
#        \
#         5
# Searching for 5 scans all 5 nodes — O(n), not O(log n)
# Solution: use a self-balancing BST (AVL tree, Red-Black tree)

Complexity Table

Operation	Balanced	Degenerate	Note
Search	O(log n)	O(n)	Height determines cost
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Min / Max	O(log n)	O(n)	Leftmost / rightmost node
In-order	O(n)	O(n)	Produces sorted output
Space	O(n)	O(n)	Call stack O(h)