Binary Search Tree — Sorted Structure

What is it? #

A binary search tree keeps one rule at every node: everything in the left subtree is smaller, everything in the right subtree is larger.

That rule means searching works like binary search. Compare with the current node and go left or right, halving the remaining possibilities at each step.

The catch is balance. If you insert already-sorted values, every new node goes to the right and the tree becomes a straight line — a linked list with extra steps, and lookups become O(n).

Self-balancing variants such as AVL and red-black trees rotate nodes during insertion to keep the height near log n. That is what real implementations use.

Think of it like this #

A well-organised filing cabinet where every drawer splits the remaining files in half: names before M in one direction, after M in the other. Finding a file takes a few decisions instead of a full search.

Now imagine filing everyone in alphabetical order into a chain of single drawers, each pointing to the next. The rule is still followed, but the shortcut is gone — that is an unbalanced tree.

Simple example #

You maintain a leaderboard where scores are inserted continuously and you need both fast lookup and the ability to list everything in order. A BST gives you both, provided it stays balanced.

Code #

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


def insert(root, value):
    if root is None:
        return BSTNode(value)
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    return root                        # duplicates ignored here


def search(root, value):
    while root:
        if value == root.value:
            return True
        root = root.left if value < root.value else root.right
    return False


def in_order(node, out=None):
    out = [] if out is None else out
    if node:
        in_order(node.left, out)
        out.append(node.value)
        in_order(node.right, out)
    return out


def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))


root = None
for value in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, value)

print(search(root, 40), search(root, 45))   # True False
print(in_order(root))       # [20, 30, 40, 50, 60, 70, 80] — sorted
print(height(root))         # 3 — balanced


# The degenerate case
skewed = None
for value in [10, 20, 30, 40, 50]:          # already sorted input
    skewed = insert(skewed, value)
print(height(skewed))       # 5 — a straight line, lookups are now O(n)


# Finding the minimum: walk left until you cannot
def minimum(node):
    while node.left:
        node = node.left
    return node.value

Balanced (height 3)              Skewed (height 5)

        50                        10
      /    \                        \
    30      70                       20
   /  \    /  \                        \
  20  40  60  80                        30
                                          \
 search: ~3 steps                          40
                                             \
                                              50
                                 search: up to 5 steps

How it works #

insert walks down comparing values. Smaller goes left, larger goes right, and when it reaches an empty spot it creates the node there. The recursive reassignment root.left = insert(root.left, value) is the idiomatic way to attach the result.

search follows the same path iteratively. Each comparison eliminates one subtree, which is the binary search idea applied to a linked structure.

in_order returns sorted values for free. That is a real advantage over a hash table: a dictionary gives O(1) lookup but no order, while a BST gives O(log n) lookup plus ordered traversal and range queries.

height shows the problem. The balanced tree built from mixed input has height 3 for seven values, which is roughly log₂(7). The skewed tree built from sorted input has height 5 for five values — every lookup is a full walk.

This matters because sorted input is common. Inserting timestamps, auto-increment IDs or alphabetised names into a naive BST produces exactly the worst case.

Self-balancing trees fix it by rotating nodes when one side gets too deep. AVL trees keep strict balance and favour lookups; red-black trees allow slightly more imbalance and favour faster insertion. Both guarantee O(log n).

Real-world use #

You rarely implement a BST, but you use them constantly through other tools. Database indexes are B-trees, a generalisation of this idea. Java's TreeMap, C++'s std::map and many language standard libraries use red-black trees.

The reason to choose an ordered structure over a hash table is range queries. "All orders between two dates" or "the ten scores just above mine" are natural in a tree and awkward in a hash map.

In Python there is no built-in BST. For sorted data, a list kept ordered with bisect covers most needs, and the sortedcontainers package provides sorted collections for heavier use.

The balance problem is also why databases periodically rebuild or reorganise indexes: insertion patterns can degrade their shape over time.

Common mistakes #

• Inserting sorted data into an unbalanced BST and getting O(n) behaviour.
• Forgetting to handle duplicates explicitly — decide whether to ignore, count or allow them.
• Recursive insert or search on a deep tree, hitting the recursion limit.
• Choosing a BST when you only need key lookup — a hash table is faster.
• Mutating a node’s value in place, which can break the ordering rule.

Practice #

Add a delete(root, value) function handling three cases: a leaf, a node with one child, and a node with two children (replace with the smallest value in its right subtree). Then write range_query(root, low, high) that returns all values in a range without visiting the whole tree.