Pointer Walk

Binary Search Trees

Smaller to the left, larger to the right. Searching skips half the tree at every step, until the tree is built in sorted order and becomes a list.

Data StructuresBeginner10 min read

Fast lookups that also keep order

A sorted array can be searched very quickly with binary search. But adding a new item means shifting everything after it to make room. A hash table adds and finds items instantly, but keeps them in no order at all, so "what is the next largest?" is a slow question.

A binary search tree aims for both: quick to search, quick to add to, and always in order.

One rule

Each node holds a value and has up to two children, a left one and a right one. The rule, at every node:

Everything in the left subtree is smaller. Everything in the right subtree is larger.

That rule turns every comparison into a decision that discards part of the tree.

Inserting 50, 30, 70, 20, 40, 60, 80Interactive

Start. An empty tree. The rule for every node: smaller values go somewhere to its left, larger values somewhere to its right.

Comparisons this step
0
Levels in the tree
0

Searching

  1. Start at the root

    Compare the value you want with the root's value.

  2. Equal? Found

    Stop.

  3. Smaller? Go left. Larger? Go right

    The entire other side is ruled out. You never look at it.

  4. Repeat until you find it or run out of tree

    Reaching an empty spot means the value is not there.

Inserting works the same way: walk down as if searching, and put the new value in the empty spot where the walk ends.

python
def search(node, target):
    while node is not None:
        if target == node.value:
            return node
        node = node.left if target < node.value else node.right
    return None

In the demo, finding 60 among seven values took 3 comparisons. With a tree like that, each step down halves what is left.

Values in a well-shaped treeLevels to walk
73
1,00010
1,000,00020
1,000,000,00030

Reading it in order

Because of the rule, visiting "left subtree, then the node, then right subtree" at every node gives all the values in sorted order. No sorting step is needed: the order is built into the shape. See Depth-First Tree Traversal.

That also makes ordered questions cheap:

  • Smallest value: keep going left.
  • Largest: keep going right.
  • Everything between 30 and 60: walk to 30, then read in order until past 60.

The catch: the shape depends on the order of insertion

Now insert the same seven values in sorted order.

Inserting 20, 30, 40, 50, 60, 70, 80Interactive

Start. An empty tree. The rule for every node: smaller values go somewhere to its left, larger values somewhere to its right.

Comparisons this step
0
Levels in the tree
0

Every new value is larger than everything before it, so it always goes to the right. The "tree" has one branch. It is a linked list wearing a disguise.

Searching it means walking past every node: 7 comparisons for 7 values, a million for a million. Everything that made the tree fast is gone.

Sorted input is not a rare accident. Data often arrives in order: timestamps, ids that count upwards, an alphabetical list.

Inserting 50, 30, 70, 20, 40, 60, 80Interactive
Inserted in

Start. An empty tree. The rule for every node: smaller values go somewhere to its left, larger values somewhere to its right.

Comparisons this step
0
Levels in the tree
0

The fix: keep it balanced

A self-balancing tree fixes its own shape as it goes. After each insert or delete it checks whether one side has become too deep, and if so, rearranges a few nodes locally (an operation called a rotation) to even things out. The values and the ordering rule are untouched. Only the shape changes.

Well-known kinds are red-black trees and AVL trees. They guarantee the tree stays about log n levels deep, whatever order the data arrives in.

You rarely write one yourself. They are what sits behind the ordered collections in standard libraries: TreeMap in Java, std::map in C++, and sorted containers in other languages.

When to use one

You needUse
Lookups by key onlyA hash table: simpler and faster
Lookups and sorted order, ranges, nearest valueA balanced search tree
The smallest item repeatedlyA heap
Data that never changes, searched oftenA sorted array with binary search

Key takeaways

  • In a binary search tree, smaller values go left of a node and larger values go right.
  • Searching follows one path down, discarding the other side at every step.
  • A well-shaped tree of a million values is only 20 levels deep.
  • Inserting values in sorted order produces a chain, and every operation becomes slow.
  • Self-balancing trees rearrange themselves to stay shallow, and are what real libraries use.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    8 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress