Binary Search Trees

A binary search tree is the simplest structure that keeps data sorted at every moment — not a sorted array you rebuild, but a living rule you preserve with each insert and delete.

The rule is one sentence: at every node, all values in the left subtree are smaller, and all values in the right subtree are larger. From that single rule, everything else — fast search, sorted reading, quick min and max — falls out on its own.

Following the rule

Searching is just the binary-search game played on a tree. At each node you ask one question — is my target smaller or larger? — and step left or right accordingly, never looking at the other side. Let us search for 6 in this tree:

Both search and insert do the same walk: start at the root, compare, step down, until you either find the value or reach an empty spot where it belongs. So both cost about the height of the tree — one comparison per level.

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

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    return root

def inorder(root, out):
    if root:
        inorder(root.left, out)
        out.append(root.val)         # root in the middle → ascending order
        inorder(root.right, out)
    return out

root = None
for v in [8, 3, 10, 1, 6, 14]:
    root = insert(root, v)

print("in-order:", inorder(root, []))

in-order: [1, 3, 6, 8, 10, 14]

That sorted output is no accident. Because every left subtree holds smaller values and every right subtree larger ones, walking left → root → right reads the tree in ascending order — a free O(n) sort once the values are in.

The height is everything

Each operation costs O(h), where h is the height — so the question that decides a BST’s whole performance is: how tall does it get?

• Balanced, where each node’s two sides stay roughly even: the height is about log₂ n, so search, insert, and delete are O(log n). A million balanced nodes is only about 20 levels.
• Degenerate: insert values in sorted order and every one is larger than the last, so each goes right, and the tree collapses into a right-leaning chain of height n. Now a “search” walks all n nodes — no better than a linked list.

Deleting takes a little more care

Removing a node can break the rule for everything beneath it, so there are three cases. A leaf just goes. A node with one child is spliced out — its parent adopts the lone child. A node with two children is the tricky one: you find its in-order successor (the smallest value in its right subtree), copy that value up into the node, then delete the successor — which, being the leftmost of a subtree, is itself a leaf or one-child case. Each delete still follows one path down, so it stays O(h).

Keeping it balanced

The degeneration is exactly why self-balancing trees exist. They add one rule on top of the BST rule and fix any violation with a rotation — a local relink of a few pointers that lowers height without disturbing the ordering.

• An AVL tree keeps the two sides of every node within one level of each other, rebalancing eagerly — height stays very close to log n.
• A red-black tree uses a looser colouring rule, so it rotates less on average. It backs most standard-library ordered maps: Java’s TreeMap, C++‘s std::map.

You will rarely implement one — the libraries are excellent — but you need to recognise the problem they solve, so you reach for the right tool when sorted inserts threaten.

Practice