---
title: 'Binary Search Trees'
source: 'https://academia.sh/en/courses/data-structures/binary-search-trees'
course: 'Data Structures'
language: en
updated: '2026-08-17T18:08:00+00:00'
license: 'CC BY-SA 4.0'
---

# Binary Search Trees

The ordering invariant, search–insert–delete operations, the three deletion cases, and the degenerate tree problem.

The previous lesson showed that traversing every node of a tree is $O(n)$. This is
not good enough for search; linear search in an array has the same cost, and the
tree provides no gain at all.

The gain appears once an **ordering** is added to the tree. If which branch to take
at every node can be determined by a comparison, search traverses only a single
path, not the whole tree.

## The Ordering Invariant

A **binary search tree** is a binary tree that satisfies the following condition at
every node:

> Every value in the left subtree is smaller than the node's value, and every value
> in the right subtree is larger.

The condition must hold for the **entire subtree**; looking only at the immediate
children is not enough. This is an **invariant** in the sense defined in the
Programming Fundamentals course: it must remain true before and after every
operation.

```
            (12)
           /    \
        (7)      (25)
       /   \        \
    (3)    (10)     (30)
```

In this tree, every value in the subtree rooted at `25` is greater than $12$; every
value in the subtree rooted at `7` is smaller. The same condition holds separately
at every node.

The invariant has a direct consequence connected to the previous lesson: **inorder
traversal gives the values in ascending order.** Because the left subtree is
traversed first, then the node is visited, and finally the right subtree is
traversed, the order arises on its own.

## Search

Search starts at the root and makes a single comparison at every node:

- If the target value equals the node, it has been found.
- If it is smaller, descend into the left subtree; if larger, into the right
  subtree.
- If an empty link is reached, the value is not in the tree.

At every step, one of the subtrees is eliminated entirely. This is the tree
counterpart of binary search on a sorted array, and its cost is proportional to
**height**.

```python
class BSTNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: "BSTNode | None" = None
        self.right: "BSTNode | None" = None


def search(root: BSTNode | None, target: int) -> tuple[bool, int]:
    """Searches for the target; returns (found, comparison count)."""
    steps = 0
    node = root
    while node is not None:
        steps += 1
        if target == node.value:
            return True, steps
        node = node.left if target < node.value else node.right
    return False, steps


def insert(root: BSTNode | None, value: int) -> BSTNode:
    """Places the value in its position; returns the root. A duplicate is not inserted."""
    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


def inorder(node, result=None):
    result = [] if result is None else result
    if node is not None:
        inorder(node.left, result)
        result.append(node.value)
        inorder(node.right, result)
    return result


root = None
for value in (12, 7, 25, 3, 10, 30):
    root = insert(root, value)

print(inorder(root))        # [3, 7, 10, 12, 25, 30]  — sorted
print(search(root, 10))     # (True, 3)
print(search(root, 11))     # (False, 3)
```

The value `10` is found in three comparisons: `12 → 7 → 10`. In this six-element
tree, linear search would make six comparisons in the worst case.

## Insertion

Insertion is a failed search: the position where the value should sit is searched
for, and once an empty link is reached, the new node is attached there. The new node
is always a **leaf**; no existing link changes.

This simplicity also preserves the ordering invariant on its own: since the node is
placed at the end of the search path, it already satisfies the conditions of all its
ancestor nodes.

What happens with duplicate values is a design decision: they can be ignored,
placed in the right subtree, or tracked with a counter in the node. The
implementation above chose the first option; if multiset behavior is wanted, the
counter approach is suitable.

## Deletion: Three Cases

Deletion is the most delicate operation on a tree; there are three cases depending
on the number of children the deleted node has.

**Leaf node.** It is removed directly; the parent's corresponding link is cleared.

**Single-child node.** The node is removed, and its one child is attached in its
place. The entire subtree is effectively moved up; the ordering invariant is
preserved.

**Two-child node.** It cannot be removed directly — two subtrees do not fit into
one link. The solution is to replace the node's value with its **successor**: the
smallest value in the right subtree. This value can take its place because it is
larger than the deleted node but smaller than every value in the right subtree.
Since the successor node cannot have a left child, deleting it reduces to one of the
first two cases.

```python
def smallest(node: BSTNode) -> BSTNode:
    while node.left is not None:
        node = node.left
    return node


def delete(root: BSTNode | None, value: int) -> BSTNode | None:
    if root is None:
        return None
    if value < root.value:
        root.left = delete(root.left, value)
    elif value > root.value:
        root.right = delete(root.right, value)
    else:
        if root.left is None:                 # leaf or single child (right)
            return root.right
        if root.right is None:                # single child (left)
            return root.left
        succ = smallest(root.right)           # two children: replace with successor
        root.value = succ.value
        root.right = delete(root.right, succ.value)
    return root


root = None
for value in (12, 7, 25, 3, 10, 30):
    root = insert(root, value)

root = delete(root, 3)            # leaf
print(inorder(root))        # [7, 10, 12, 25, 30]

root = delete(root, 25)           # single child
print(inorder(root))        # [7, 10, 12, 30]

root = delete(root, 12)           # two children: the root
print(inorder(root))        # [7, 10, 30]
```

Inorder traversal staying sorted after every deletion is evidence that the invariant
is preserved. This is the standard way to test a data structure's correctness:
checking the invariant after every operation.

## The Degenerate Tree Problem

The promise of a binary search tree is that all operations are proportional to
height. The value of that promise depends on the height being small — and there is
no guarantee of that.

If values are inserted in ascending order, every new node attaches to the right; the
tree turns into a linked list:

```python
ascending = None
for value in (3, 7, 10, 12, 25, 30):        # sorted insertion
    ascending = insert(ascending, value)

mixed = None
for value in (12, 7, 25, 3, 10, 30):        # balanced order
    mixed = insert(mixed, value)

print(search(ascending, 30))        # (True, 6)  — every node was traversed
print(search(mixed, 30))            # (True, 3)
```

The same six values, the same structure, a twofold difference. When input arrives
sorted — a situation frequently encountered in real data — the tree slips into its
worst case.

This is the starting point of the next three lessons: keeping the tree's height
logarithmic regardless of insertion order.

## Cost Table

| Structure | Search | Insert | Delete | Sorted traversal |
|---|---|---|---|---|
| Hash table | $O(1)$ average | $O(1)$ average | $O(1)$ average | Not supported |
| Binary search tree (balanced) | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(n)$ |
| Binary search tree (degenerate) | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ |

## Summary

- A binary search tree rests on the invariant that at every node the left subtree
  carries smaller values and the right subtree carries larger ones.
- As a consequence of the invariant, inorder traversal gives the values in
  ascending order.
- Search eliminates one subtree at every step; the cost is proportional to height.
- Insertion attaches a leaf at the end of a failed search; existing links do not
  change.
- Deletion has three cases; a two-child node is reduced to one of the first two
  cases by replacing it with the smallest value in its right subtree.
- There is no height guarantee: sorted input turns the tree into a linked list and
  all operations drop to linear.

## Next Step

The problem has been defined: height depends on insertion order. The solution is to
check the tree after every change and rearrange it when needed. The next lesson
takes up the rotation operation that performs this rearrangement, and the two
classic tree families that guarantee balance.