Trees and Binary Search Trees: A Practical Guide

What a tree and a BST are

A tree is a structure of nodes where every node except the root has one parent and zero or more children, with no cycles. File systems, the browser DOM and site menus are all trees.

A binary search tree (BST) is a tree where each node has at most two children and one rule holds:

• every key in the left subtree is smaller than the node's key;
• every key in the right subtree is larger.

Thanks to this rule, every step of a search discards half of the remaining tree, just like binary search over a sorted array. The difference is that inserts and deletes do not require shifting elements.

Implementation: insert and search

A minimal Python implementation. Duplicates are ignored here; decide on that policy up front.

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

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

def search(root, key):
    while root is not None and root.key != key:
        root = root.left if key < root.key else root.right
    return root

Insertion always adds the new node as a leaf: walk down using "smaller goes left, larger goes right" until you hit an empty spot.

Delete: three cases

Deletion is the trickiest operation. There are three situations:

1. The node has no children: just remove it.
2. One child: put the child in the node's place.
3. Two children: find the in-order successor (the smallest key in the right subtree), copy its key into the node, then delete the successor from the right subtree.

def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left is not None:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root

The successor never has a left child, so removing it falls back to case 1 or 2.

Traversals

def inorder(root):
    if root is not None:
        yield from inorder(root.left)
        yield root.key
        yield from inorder(root.right)

If an in-order traversal of your tree produces an unsorted sequence, the implementation has a bug. That makes it a handy check in tests.

Why balance matters

BST speed depends on the tree's height. In a balanced tree the height grows like log n, so search, insert and delete run in O(log n).

But if you insert already sorted data (1, 2, 3, 4…), every new node goes to the right and the tree degenerates into a linked list. Operations become O(n), and recursive functions may hit the stack depth limit.

In practice data often arrives sorted: database ids, dates, spreadsheet imports. That is why a plain BST is rarely used in production.

AVL and red-black trees

Self-balancing trees restore balance after every insert and delete using rotations: a local rearrangement of a few nodes that preserves key order.

• An AVL tree stores a height in each node and keeps the heights of the left and right subtrees within 1 of each other. Balance is strict, so lookups are fast, but updates may need more rotations.
• A red-black tree colors nodes in two colors and enforces rules under which the longest root-to-leaf path is at most twice as long as the shortest. Balance is looser, but inserts and deletes are usually cheaper.

Red-black trees power many standard libraries, for example Java's TreeMap. Writing one yourself is a good exercise; in production code use a ready-made implementation.

Common mistakes

• Checking the BST rule only against direct children instead of the whole subtree.
• Not deciding up front how to handle duplicates.
• Forgetting to return the new root from a recursive delete.
• Using a BST where a hash table is enough: if you need neither key order nor range queries, a dictionary is simpler and faster.