18. Binary Search Tree

What you'll learn

• 1Implement insert, search, and delete on a BST
• 2Understand why unbalanced BSTs degenerate to O(n)
• 3Know when to reach for a balanced tree (AVL, Red-Black) or skip-list

Overview

A BST maintains the property: for every node, left subtree < node < right subtree. Search and insert are O(log n) on average. The catch is balance — a sequence of sorted inserts produces a linked list with O(n) operations.

Core Concepts

1. Insert

def insert(root, val):
    if not root:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

2. Search

def search(root, target):
    while root:
        if root.val == target: return root
        root = root.left if target < root.val else root.right
    return None

3. Delete (the tricky one)

def delete(root, val):
    if not root: return None
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        # Found node to delete
        if not root.left:  return root.right
        if not root.right: return root.left
        # Two children: replace with smallest from right subtree
        succ = root.right
        while succ.left:
            succ = succ.left
        root.val = succ.val
        root.right = delete(root.right, succ.val)
    return root

4. The balance problem

Insert 1, 2, 3, 4, 5 into an empty BST:

  1                Degenerate into a linked list.
   \               Height = N → all ops O(n).
    2              No better than a list!
     \
      3
       \
        4
         \
          5

5. Balanced trees in production

• AVL trees: strict balance, faster lookup, slower insert.
• Red-Black trees: looser balance, used in C++ std::set, Java TreeMap.
• Skip lists: probabilistic alternative.
• In Python, use sortedcontainers.SortedList for production code.

Examples

Example 1 — src/01_bst.py

Build a BST with insert/search/delete.

Example 2 — src/02_inorder_sorted.py

Confirm inorder of a BST is sorted.

Example 3 — src/03_unbalanced_demo.py

Insert in sorted order to see worst-case O(n) behavior.

Example 4 — src/04_sorted_list.py

Use sortedcontainers.SortedList — the practical choice for competitive Python.

Common Mistakes

1. Trying to implement AVL/Red-Black during a contest — too slow. Use SortedList.
2. Forgetting BST without balance degenerates to O(n).
3. Off-by-one in delete-with-two-children: pick wrong successor.
4. Allowing duplicates without deciding on a convention (left or right).

Recap

• BST: left subtree < node < right subtree.
• Balance is what makes BSTs O(log n).
• In Python, prefer sortedcontainers over custom BSTs.

Try It

1. BOJ 5639 (Binary search tree).
2. Insert numbers 1..10 in random order and verify inorder gives sorted output.