Trees and choosing a structure

Binary search trees, why balance decides everything, heaps for priority, and a decision table for real code.

Binary search trees

A binary search tree keeps every key in the left subtree smaller than the node and every key in the right subtree larger. That single invariant makes lookup, insert and delete O(height), so the height is the whole story: O(log n) when balanced and O(n) when the insertion order is unkind.

class Node:
    __slots__ = ('key', 'left', 'right')

    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)     # equal keys are ignored here
    return root

def inorder(node, out=None):
    """Sorted order, in O(n)."""
    out = [] if out is None else out
    if node is None:
        return out
    inorder(node.left, out)
    out.append(node.key)
    inorder(node.right, out)
    return out

def contains(root, key):
    while root is not None:
        if key == root.key:
            return True
        root = root.left if key < root.key else root.right
    return False

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

# Sorted input produces a linked list in disguise: height n, every op O(n)
skewed = None
for k in [1, 2, 3, 4, 5]:
    skewed = insert(skewed, k)
print('skewed height:', height(skewed))       # 5 for 5 keys

balanced = None
for k in [5, 3, 8, 1, 4]:
    balanced = insert(balanced, k)
print('balanced height:', height(balanced))   # 3 for 5 keys
print(inorder(balanced))                      # [1, 3, 4, 5, 8]
print(contains(balanced, 4), contains(balanced, 9))

• In-order traversal of a valid BST always yields sorted output, which is the cheapest way to verify the invariant while debugging.
• Deleting a node with two children means replacing it with its in-order successor (the smallest key in the right subtree) to keep the ordering.
• Inserting sorted or reverse-sorted data into a naive BST builds the worst possible shape, which is why self-balancing variants exist.
• AVL trees keep heights within one level of each other and are read-optimised; red-black trees allow a slightly larger imbalance but need fewer rotations, so they are better under mixed read and write load.
• A tree also gives ordered traversal and range queries, which a hash table cannot do at all.

Balanced trees and heaps

import heapq
import bisect

# A heap is a complete tree in a flat array: parent i has children 2i+1 and 2i+2
nums = [5, 1, 8, 3]
heapq.heapify(nums)                 # O(n), in place, no extra memory
print(nums[0])                      # 1: the minimum is always at the root
heapq.heappush(nums, 2)             # O(log n)
smallest = heapq.heappop(nums)      # O(log n)
print(smallest, nums, heapq.nlargest(2, nums))

# A max heap is a min heap of negated values, the usual Python workaround
maxh = []
for x in (5, 1, 8):
    heapq.heappush(maxh, -x)
print(-heapq.heappop(maxh))         # 8

# A sorted list plus bisect gives ordered lookup without a tree, until inserts grow
ordered, data = [], {}
for k, v in (('a', 1), ('c', 3), ('b', 2)):
    data[k] = v
    i = bisect.bisect_left(ordered, k)
    if i == len(ordered) or ordered[i] != k:
        ordered.insert(i, k)
print(ordered, ordered[bisect.bisect_left(ordered, 'b')])

# Range query: O(log n) to find the boundary, then a linear walk
print([k for k in ordered if 'a' <= k <= 'b'])

B+trees are what databases actually use: a very high branching factor keeps the height at three or four levels for millions of rows, and the leaves are linked so a range scan reads sequentially instead of jumping around the file.

When to use what

import heapq
from collections import OrderedDict, deque

# Real code usually composes two structures instead of finding one perfect one

# 1. Hash table for lookup plus a list for order
index, order = {}, []
def add(record):
    index[record['id']] = record
    order.append(record['id'])

# 2. Hash table of heaps: group by key, keep the worst first per group
slowest = {}
def record_latency(route, ms):
    bucket = slowest.setdefault(route, [])
    heapq.heappush(bucket, -ms)             # max heap per route
    if len(bucket) > 3:
        heapq.heappop(bucket)               # keep only the three slowest

# 3. deque as a sliding window, hash table for the running count
window, counts = deque(), {}
def push_value(v, limit=3):
    window.append(v)
    counts[v] = counts.get(v, 0) + 1
    if len(window) > limit:
        old = window.popleft()
        counts[old] -= 1
        if counts[old] == 0:
            del counts[old]

print('ok')

FAQ

Related

Hash tables Sorting and searching

Last refreshed 2026-09-18.