Skip to content
← Back to algorithms

Step 0 / 0 · Comparisons: 0 · Swaps: 0

How this algorithm works

How it works

  1. Start at the root with the value to insert.
  2. If the value is smaller, go left; if larger, go right.
  3. If the value is already there, stop — a set holds it once.
  4. When the next step would leave the tree, that empty slot is the destination.
  5. Attach the new node there and stop.
  6. Repeat for the next value.

Key concepts

  • Ordering invariant: left < node < right, everywhere
  • An in-order walk reads the values back sorted
  • Insertion order decides the shape, and the shape decides the speed
  • Sorted input produces a spine — O(n) lookups, no better than a list

When to use it

When you need ordered data with fast lookup, insertion and in-order traversal, and the input order is not adversarial. If it might be, use a self-balancing tree.

Did you know

Insert 1 through 7 in order and you get a seven-level spine. Insert 4, 2, 6, 1, 3, 5, 7 and you get three levels — same values, same algorithm.