Q&A

What is a 2-3 Tree?

By AlgoInsight Team2026-06-18algorithmsdata-structures

Overview

Binary search trees can degrade to O(n) when unbalanced. A 2-3 tree stays balanced by allowing internal nodes to temporarily hold two keys and three children, then splitting overfull nodes upward and merging underfull nodes on deletion - keeping all leaves at exactly the same level. The result is guaranteed O(log n) regardless of input order.

graph TD
    A["[10 | 20]<br/>2-key node (3-node)"] --> B["[5]<br/>2-node"]
    A --> C["[15]<br/>2-node"]
    A --> D["[25]<br/>2-node"]
    B --> L1[" 3 "]
    B --> L2[" 7 "]
    C --> L3[" 12 "]
    C --> L4[" 18 "]
    D --> L5[" 22 "]
    D --> L6[" 30 "]
    style A fill:#1e1b4b,color:#fff

Node Types

• 2-node - holds 1 key, has 2 children. Left child keys < key; right child keys > key.
• 3-node - holds 2 keys (small, large), has 3 children. Left < small < middle < large < right.

All leaves are at the same level - this is the invariant that ensures balance.

Search

Searching is like a binary search tree, but at each 3-node you compare against two keys to decide which of three subtrees to follow:

To find k in node [a | b]:
  if k < a → go left
  if a < k < b → go middle
  if k > b → go right

At most log₂ n comparisons.

Insertion

Insert into the appropriate leaf. If the leaf becomes a 4-node (3 keys), split it:

1. The middle key moves up to the parent.
2. The two outer keys become two separate 2-nodes (children of the parent).
3. If the parent also overflows, split it too (propagating upward).
4. If the root splits, a new root is created - this is how the tree grows in height.

Insert 15 into [10 | 20] (a 3-node leaf):
→ Temporary 4-node [10 | 15 | 20]
→ Split: middle key 15 becomes root, 10 and 20 become children

Deletion

Deletion is more complex, but the key idea is:

• Delete the key; if a leaf becomes empty, merge it with a sibling and pull a key down from the parent.
• If the parent underflows, merge/rotate up the tree until the root.
• The tree shrinks in height when the root becomes empty after a merge.

Complexity

All cases - not just average. This is the point: perfect balance eliminates worst-case degradation.

Why 2-3 Trees Matter

B-trees (used in databases and file systems) generalize this idea: each node can have up to t keys (t-1 to 2t-1), matching disk block sizes for efficient I/O. Red-Black trees and AVL trees are other self-balancing approaches; RB-trees can be mapped exactly to 2-3-4 trees. Understanding 2-3 trees is the clearest path to grasping why all these balanced-tree structures work.

2-3 vs Binary Search Tree vs B-tree

Why This Matters in Interviews

Algorithms interviews use 2-3 trees to test balanced-BST understanding - the question probes whether you grasp why balance matters and how splitting enforces it. Key points: the 2-node/3-node structure, that all leaves are the same depth (the invariant), insertion via splitting (middle key propagates up), that the tree grows from the root, and that 2-3 trees underpin B-trees (databases) and are isomorphic to Red-Black trees. Explaining the split mechanism clearly is the differentiator.

Common Pitfalls

• Confusing the direction of growth (the tree grows upward via root splits, not downward like BST insertion).
• Forgetting that deletion involves merging/borrowing, not just removal.
• Mixing up 2-3 trees (up to 2 keys) with 2-3-4 trees (up to 3 keys) or B-trees.
• Thinking all nodes must be 3-nodes - 2-nodes are perfectly valid and normal.

References

• 2-3 tree: https://en.wikipedia.org/wiki/2–3_tree
• Robert Sedgewick, Algorithms (4th ed.) - red-black BSTs and their 2-3 tree equivalence.

More answers