skip to content

What are the time complexities of TreeMap operations, and why does it differ from HashMap?

level: middleimportance: should knowfreq 62%

answer

  1. TreeMap = red-black (balanced BST), sorted keys
  2. get/put/remove/containsKey all O(log n)
  3. Navigation + range views (ceiling/floor/subMap) O(log n)
  4. HashMap O(1) avg but unordered; TreeMap O(log n) but ordered
  5. TreeSet = TreeMap without values, same O(log n)

basics

~10 s

TreeMap keeps keys sorted using a balanced tree, so get, put, remove, and containsKey are O(log n) — slower than HashMap's average O(1). In return you get ordered keys and fast range queries.

solid answer

~40 s

TreeMap is a red-black tree (a self-balancing binary search tree) ordered by the keys' natural ordering or a supplied Comparator. Because it stays balanced, get/put/remove/containsKey are all O(log n) — every operation walks from the root down a path whose length is logarithmic in the entry count. This is worse than HashMap's average O(1), but it buys you sorted iteration and efficient navigation: firstKey/lastKey, ceilingKey/floorKey/higherKey/lowerKey, and headMap/tailMap/subMap range views — all O(log n) to locate. So you choose TreeMap when you need ordering or range queries, and HashMap when you only need point lookups. Worth noting HashMap's worst case (collisions, treeified) also lands at O(log n), but its average O(1) is why it is the default; TreeMap's O(log n) is its consistent guaranteed cost.

go deeper

for a junior

Knows TreeMap keeps keys sorted and that its operations are O(log n), slower than HashMap.

for a middle

Explains the red-black/balanced-BST basis, why log n, and the navigation/range operations TreeMap adds.

for a senior

Contrasts the comparison-vs-hash trade-off, notes Comparable/Comparator requirements, and picks TreeMap vs LinkedHashMap vs HashMap by access pattern.

for a principal

Reasons about guaranteed vs amortized bounds for SLAs, memory/locality cost of node-based trees, and when an external sorted structure or index beats an in-memory TreeMap.

## What a TreeMap is A `TreeMap` stores **key→value** pairs like a HashMap, but it keeps the keys in **sorted order**. The ordering comes either from the keys' **natural ordering** (the key type implements `Comparable`, e.g. `Integer`, `String`) or from a **`Comparator`** you pass to the constructor. ## How it works internally Under the hood TreeMap is a **red-black tree** — a kind of **balanced binary search tree (BST)**. - A **binary search tree** is a tree where each node has at most two children; everything in the left subtree is 'less than' the node and everything in the right subtree is 'greater'. To find a key you start at the root and go left or right by comparison until you find it — like binary search. - **Balanced** means the tree's height is kept proportional to **log n** even as you insert and delete. A red-black tree enforces colour rules and rotates nodes on insert/remove to prevent it degenerating into a long chain (which would make it O(n)). ## The complexities Because the height is always ~log n, every operation that walks root-to-leaf costs **O(log n)** (logarithmic — doubling the entry count adds only one extra step): - **get / put / remove / containsKey: O(log n)** — locate by comparing keys down one path. - **firstKey / lastKey: O(log n)** — walk to the leftmost / rightmost node. - **Navigation — ceilingKey, floorKey, higherKey, lowerKey: O(log n)** — find the closest key at or beyond a target. - **Range views — headMap / tailMap / subMap: O(log n)** to locate the boundary; iterating the range is then O(k) for k elements. - **In-order iteration: O(n)** and it comes out **sorted** — a property HashMap cannot give you. ## Why it differs from HashMap HashMap uses **hashing**: it computes a bucket from the key's hash and jumps straight there, giving **average O(1)** but **no ordering** at all (iteration order is unspecified). TreeMap uses **comparison**: it cannot 'jump' to a key; it must navigate the ordered tree, costing **O(log n)** — but that same comparison-based structure is exactly what yields sorted order and range queries. Note the worst cases converge: a HashMap with many collisions (treeified, Java 8+) also reaches O(log n). The difference is HashMap is O(1) *on average* while TreeMap is O(log n) *always* — a predictable, guaranteed bound. ## The same applies to TreeSet `TreeSet` is a TreeMap of keys with no values — `add`/`remove`/`contains` are likewise O(log n) and iteration is sorted. ## When to use which - Need only point lookups, fastest possible, order irrelevant → **HashMap**. - Need keys sorted, or range/nearest-key queries (e.g. 'all entries between A and B', 'smallest key >= x') → **TreeMap**. - Need insertion-order iteration with hash speed → **LinkedHashMap** (a third option, average O(1) with predictable order).

  • When would you choose a TreeMap over a HashMap despite the slower lookups?
    When you need keys in sorted order, or range/nearest-neighbour queries — firstKey/lastKey, ceilingKey/floorKey, or subMap/headMap/tailMap. HashMap offers none of these; its iteration order is unspecified.
  • What is the complexity of iterating all entries of a TreeMap, and in what order?
    O(n) — an in-order traversal visits every node once — and the entries come out in sorted key order, which is the defining advantage over HashMap.

saying these in an interview costs you the question

  • Saying TreeMap is O(1) like HashMap (it is O(log n) for all core ops)
  • Forgetting TreeMap requires keys to be Comparable or need a Comparator (else ClassCastException on put)
  • Claiming TreeMap iteration is unordered (it is sorted)
  • Confusing TreeMap with LinkedHashMap (insertion order, hash-backed)

context

resolving links…