2-3 Tree

Perfectly balancedO(log n)

A B-tree of order 3: every node holds 1 key (2-node) or 2 keys (3-node), and all leaves sit at the same depth. Balance is maintained by splitting any overstuffed 4-node and promoting its middle key — no rotations needed. The tree only grows in height when the root itself splits.

Keys (n)

Height

Log₂(n)

In-order traversal (sorted output)

Preset tree loaded. Insert/search keys, run a traversal, or try a Random Lesson.

Operations

Custom list demo

Traversal / search order

Legend

highlighted (visiting)

splitting (4-node → 2+2)

2-node (1 key)

3-node (2 keys)

Rules of insertion

Insert into a 2-node leaf

Becomes a 3-node (2 keys, 0 children). No structural change.

Insert into a 3-node leaf

Forms a transient 4-node — split: left + right become 2-nodes, middle key promotes to parent.

Promotion into a 2-node parent

Parent absorbs the new key, becomes a 3-node. Done.

Promotion into a 3-node parent

Parent becomes a transient 4-node — split again, promote upward. Cascades to root if needed.

Promotion into a 3-node root

Root splits — a new root containing only the promoted key is created. Tree height increases by exactly 1.

All leaves stay at one depth

Because splits only ever add levels at the root, every leaf grows in lock-step. Height ≤ log₂(n+1).

Complexity

search(k)O(log n)

insert(k)O(log n)

delete(k)O(log n)

in-orderO(n)