Binary Search
Trees

Definition

A Binary Search Tree is a rooted binary tree where every node satisfies the BST invariant:

• All keys in the left subtree are strictly less than the node's key
• All keys in the right subtree are strictly greater than the node's key
• Both left and right subtrees are themselves valid BSTs

Node structure

class Node:
    key:    int
    value:  any
    left:   Node | None
    right:  Node | None

Visual example

Algorithm

Starting at the root, compare the target key k with the current node's key:

• k == node.key — found, return node
• k < node.key — recurse into left subtree
• k > node.key — recurse into right subtree
• node == null — key not present

Recursive

def search(node, key):
    if node is None:
        return None
    if key == node.key:
        return node
    elif key < node.key:
        return search(node.left, key)
    else:
        return search(node.right, key)

Iterative variant

def search_iterative(node, key):
    while node is not None:
        if key == node.key:
            return node
        elif key < node.key:
            node = node.left
        else:
            node = node.right
    return None

Search trace example

Searching for key 7 in the example tree:

3 comparisons — O(log 9) ≈ 3.2

Algorithm

Insertion follows the same path as search. When we reach a null pointer, we create a new node there.

def insert(node, key, value):
    if node is None:
        return Node(key, value)
    if key < node.key:
        node.left = insert(node.left, key, value)
    elif key > node.key:
        node.right = insert(node.right, key, value)
    else:
        node.value = value  # duplicate: update
    return node

Insertion order matters

    4
   / \
  2   6
 / \ / \
1  3 5  7

1
 \
  2
   \
    3
     \
      ...

Three cases

Pseudocode

def delete(node, key):
    if node is None:
        return None
    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        # Two children: in-order successor
        succ = find_min(node.right)
        node.key = succ.key
        node.value = succ.value
        node.right = delete(
            node.right, succ.key)
    return node

In-order successor

The node with the smallest key greater than a given node's key.

def find_successor(node):
    if node.right:
        return find_min(node.right)
    parent = node.parent
    while parent and node == parent.right:
        node = parent
        parent = parent.parent
    return parent

In-order predecessor

The mirror: largest key smaller than the given node.

Four traversal orders

In-order traversal

def inorder(node, result):
    if node is None:
        return
    inorder(node.left, result)
    result.append(node.key)
    inorder(node.right, result)

Problem

Given a sorted array, build a height-balanced BST (minimise height).

Algorithm

Pick the middle element as root. Recursively build the left subtree from the left half and the right subtree from the right half.

def sorted_array_to_bst(arr, lo, hi):
    if lo > hi:
        return None
    mid = (lo + hi) // 2
    node = Node(arr[mid])
    node.left  = sorted_array_to_bst(
        arr, lo, mid - 1)
    node.right = sorted_array_to_bst(
        arr, mid + 1, hi)
    return node

Complexity

Result for [1..7]

Time complexity by operation

Space complexity

• Storage: O(n) for n nodes
• Recursive ops: O(h) stack space
• Balanced: h = O(log n)
• Degenerate: h = O(n)

Average-case analysis

What goes wrong

When keys are inserted in sorted order, each new node becomes a right child. The tree degenerates into a linked list.

1
 \
  2
   \
    3
     \
      4
       \
        5

    3
   / \
  1   4
   \   \
    2   5

Performance impact

Real-world triggers

• Auto-incrementing IDs inserted in order
• Alphabetically sorted data (names, cities)
• Time-series data with monotonic timestamps
• Sequential log entries

The guarantee

A balanced BST maintains h = O(log n) after every insertion and deletion, ensuring worst-case O(log n) operations.

Balance criteria comparison

The cost of balance

Balancing requires extra work on each insert/delete — typically rotations:

Idea

If insertion order determines tree shape, and random order gives O(log n) expected height, can we simulate random order?

Approach 1 — Shuffle then insert

Randomly permute the keys before insertion. Simple but requires all keys up front (offline).

Approach 2 — Randomised insertion

On inserting a key into a subtree of size n, with probability 1/(n+1) insert it at the root of the subtree (using rotations). Otherwise, recurse normally.

Implementation

def rand_insert(node, key):
    if node is None:
        return Node(key)
    if random() < 1.0 / (size(node) + 1):
        return insert_at_root(node, key)
    if key < node.key:
        node.left = rand_insert(
            node.left, key)
    else:
        node.right = rand_insert(
            node.right, key)
    return node

Properties

• Each key equally likely to be root of any subtree
• Expected height: O(log n)
• No worst-case guarantee — but bad trees are exponentially unlikely

Definition

A treap is a BST where each node has a key (BST order) and a random priority (heap order). The tree simultaneously satisfies:

• BST property on keys — left < node < right
• Max-heap property on priorities — parent ≥ child

Operations

Structure

Concept

An augmented BST stores additional information in each node to support extra queries efficiently. The augmented data must be maintainable during rotations in O(1).

Order statistics tree

Each node stores size — the number of nodes in its subtree (including itself).

Supported operations

Structure

Select algorithm

def select(node, k):
    left_size = size(node.left)
    if k == left_size + 1:
        return node
    elif k <= left_size:
        return select(node.left, k)
    else:
        return select(node.right,
                      k - left_size - 1)

Problem

Given a set of intervals [lo, hi], efficiently find all intervals that overlap a query interval or point.

Augmentation

Each node stores an interval [lo, hi] as its key (ordered by lo), plus max_hi — the maximum hi value in its subtree.

Overlap query

def query_overlap(node, lo, hi):
    if node is None:
        return []
    results = []
    if overlaps(node.interval, (lo, hi)):
        results.append(node.interval)
    if node.left and node.left.max_hi >= lo:
        results += query_overlap(
            node.left, lo, hi)
    if node.right and \
       node.right.interval.lo <= hi:
        results += query_overlap(
            node.right, lo, hi)
    return results

Structure

Applications

Definition

An AVL tree (Adelson-Velsky and Landis, 1962) is a BST where for every node, the heights of the left and right subtrees differ by at most 1.

Balance factor

balance_factor(node) = height(left) - height(right)
# Valid values: -1, 0, +1
# Any other value triggers rebalancing

Properties

• Height bound: h < 1.44 × log2(n + 2)
• Search: O(log n) worst case
• Insert: O(log n) — at most 2 rotations
• Delete: O(log n) — up to O(log n) rotations

Rotations

Right rotation (LL case)

Five properties

1. Every node is red or black
2. The root is black
3. Every null leaf is black
4. Red nodes have only black children
5. All paths from a node to its null descendants have the same black-height

Height guarantee

Longest path (alternating red-black) is at most 2× the shortest (all black):

h ≤ 2 × log2(n + 1)

AVL vs Red-Black

Example structure

Idea

A self-adjusting BST that moves the most recently accessed node to the root via rotations called splaying. No balance metadata stored.

Splay operations

Amortised analysis

• No single operation guaranteed O(log n)
• m operations on n-node tree: O(m × log n) total
• Amortised cost per operation: O(log n)

Advantages

Problem

Provide an iterator that returns BST elements in sorted (in-order) order, using O(h) space and O(1) amortised time per next() call.

Stack-based approach

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def has_next(self):
        return len(self.stack) > 0

    def next(self):
        node = self.stack.pop()
        self._push_left(node.right)
        return node.key

Complexity

Morris traversal alternative

Key takeaways

• The BST invariant (left < node < right) enables O(log n) search, insert, and delete — but only when balanced
• Degenerate BSTs reduce to linked lists with O(n) operations — insertion order is everything
• Balancing strategies (AVL, Red-Black, treaps, splay) restore O(log n) guarantees at minimal overhead
• Augmented BSTs (order statistics, interval trees) answer richer queries without changing asymptotic complexity
• Treaps combine BST + heap using random priorities for expected O(log n) height
• Splay trees achieve amortised O(log n) through access-driven restructuring
• The stack-based BST iterator provides O(h) space, O(1) amortised traversal
• BSTs underpin databases, operating systems, and compilers

Recommended reading