ReviseAlgo Logo

Collections Framework

TreeMap

Analyze TreeMap sorted key structures, Red-Black balancing trees, and NavigableMap range operations.

Interview: Focuses on Red-Black tree properties, O(log N) runtime bounds, Comparable key requirements, and range methods.

Last Updated: June 13, 2026 • 10 min read

A TreeMap is a Red-Black tree based implementation of the NavigableMap interface. It ensures keys are sorted based on their natural ordering or a custom Comparator.

Red-Black Tree

Data is organized in a self-balancing binary search tree, preventing worst-case degradation.

Logarithmic Cost

Guarantees O(log N) time complexity for key operations like containsKey, get, put, and remove.

Navigable Views

Provides range and boundary lookup queries: firstEntry, lastEntry, ceilingKey, and floorKey.

Sorted Range Operations

TreeMap provides methods to extract subsets of the map:

  • subMap(fromKey, toKey): Returns a view of the portion of the map whose keys range from fromKey to toKey.
  • headMap(toKey): Returns a view of the map containing keys strictly less than toKey.
  • tailMap(fromKey): Returns a view of the map containing keys greater than or equal to fromKey.

Common Pitfalls

  • Comparable mismatch: Using custom classes as keys without implementing Comparable, which throws a ClassCastException on insertion.
  • Null key insertions: Storing null keys, which raises a NullPointerException during sorting operations.

Best Practices

  • Consistent comparator contracts: Ensure the comparator's compare(a, b) returns 0 if and only if a.equals(b) returns true.
  • Avoid for unsorted lookups: Use HashMap for standard lookups to get constant-time O(1) performance instead of TreeMap's O(log N) logarithmic time.

Interview-Relevant Information

Q1: What are the worst-case complexities of TreeMap operations?
Answer: TreeMap guarantees O(log N) time complexity for insertions, deletions, and lookups, even in the worst-case. This is ensured by the self-balancing Red-Black binary search tree structure.

Q2: Why does TreeMap reject null keys?
Answer: Keys must be compared to existing keys to determine their position in the Red-Black tree. A null key cannot be compared, so it raises a NullPointerException.

Quick Checklist

Can you identify the self-balancing binary tree type used in TreeMap, state operation complexities, and explain how range view operations behave? If yes, you understand TreeMap.

Use Cases

Building scheduling systems sorted by timestamp keys.

Implementing directory structures that require prefix range matching.

Common Mistakes

Using mutable keys that alter sorting order.

Failing to supply a Comparator for non-Comparable keys.