skip to content

What data structure backs TreeMap, and why does it guarantee O(log n) operations?

level: middleimportance: should knowfreq 55%

answer

  1. Red-black tree = self-balancing BST
  2. Colour invariants bound height to ~2 log n
  3. Rotations + recolouring restore balance, O(log n)
  4. Plain BST can degenerate to O(n); RB tree cannot
  5. In-order traversal yields sorted keys

basics

~20 s

TreeMap is backed by a red-black tree, a self-balancing binary search tree. Because the tree keeps itself roughly balanced, its height stays around log n, so finding, inserting, or removing a key takes O(log n) steps.

solid answer

~40 s

TreeMap uses a red-black tree — a binary search tree that self-balances using a colour invariant (every node is red or black, with rules that no red node has a red child and every root-to-leaf path has the same number of black nodes). These invariants bound the tree height to at most 2·log2(n+1), so it can never degenerate into a linked list the way an unbalanced BST can. Every get/put/remove walks from the root down one path, doing O(log n) comparisons; insertions and deletions then fix violated invariants with rotations and recolourings, also O(log n). The keys' Comparable/Comparator ordering drives the comparisons at each node. This balancing is exactly why TreeMap's sorted operations and range/nearest queries are all logarithmic rather than linear.

go deeper

for a junior

Knows TreeMap is backed by a tree and that being balanced keeps it fast.

for a middle

Names the red-black tree, states the height bound, and explains why balancing gives O(log n).

for a senior

Can describe the colour invariants, rotations/recolouring, and how in-order traversal underpins sorted iteration and range views.

for a principal

Reasons about the constant factors vs other balanced trees, cache behaviour of pointer-chasing nodes, and when a different structure (B-tree, skip list) is preferable.

## Binary search tree (BST) basics A **binary search tree** is a tree where each node has up to two children, and for any node all keys in its **left** subtree are smaller and all keys in its **right** subtree are larger. To find a key you start at the **root** (top node) and go left or right by comparing, halving the search space each step. If the tree is balanced its **height** (longest root-to-leaf path) is ~log n, so search is O(log n). ## The degeneration problem A plain BST can become **unbalanced**: insert keys 1,2,3,4,5 in order and you get a straight line (each node only has a right child). Height becomes n, and search degrades to **O(n)** — no better than a list. A **self-balancing** tree prevents this. ## Red-black tree A **red-black tree** is a self-balancing BST that colours each node **red** or **black** and enforces invariants: 1. The root is black. 2. Red nodes cannot have red children (no two reds in a row). 3. Every path from a node down to a null leaf contains the **same number of black nodes** (the 'black height'). Together these guarantee the longest path is at most **twice** the shortest, so height ≤ 2·log2(n+1). The tree stays 'bushy', never a line. ## Keeping the invariants on change When you `put` (insert) or `remove`, the new structure may violate an invariant. The tree repairs itself with: - **Rotations**: a local restructuring that pivots a node with its child to rebalance, preserving BST order. - **Recolouring**: flipping node colours. Both are O(1) per fix, and at most O(log n) fixes propagate up the tree, so insert/delete stay **O(log n)**. ## Why this matters for TreeMap Every TreeMap operation — `get`, `put`, `remove`, and the navigation methods like `floorKey`/`ceilingKey` — descends a single path of the tree using the key ordering (Comparable or your Comparator) to choose left/right. Bounded height ⇒ all are O(log n). Because the tree is ordered, an **in-order traversal** yields keys ascending in O(n), which is what iteration and the range views use. ## Contrast with HashMap HashMap reaches buckets directly by hash code (O(1) average) but has no order. TreeMap trades that constant-time access for guaranteed ordering and the logarithmic range/nearest queries the red-black structure makes possible.

  • Why can't an ordinary unbalanced BST guarantee O(log n)?
    Inserting already-sorted keys produces a degenerate, list-shaped tree of height n, making operations O(n). Self-balancing (red-black) trees rebalance to keep height ~log n.
  • What two operations restore the red-black invariants after an insert?
    Rotations (local pivots that keep BST order) and recolouring (flipping red/black). Each fix is O(1) and at most O(log n) propagate upward.

saying these in an interview costs you the question

  • Saying TreeMap uses a hash table
  • Claiming a plain (unbalanced) BST guarantees O(log n)
  • Confusing red-black tree with AVL tree as TreeMap's backing (it's red-black)
  • Thinking rotations are O(n)

context

resolving links…