# Part 6 — TreeMap & TreeSet Deep Dive

Unlike HashMap, which is optimized for fast lookup, TreeMap is optimized for ordered data.

Senior interviewers often ask:

• Why is TreeMap slower than HashMap?
• Why does Java use a Red-Black Tree instead of a Binary Search Tree (BST)?
• What are tree rotations?
• What's the difference between Comparable and Comparator?

1. What is TreeMap?¶

TreeMap is an implementation of the NavigableMap interface based on a Red-Black Tree.

Characteristics:

• Stores key-value pairs
• Keys are sorted
• Duplicate keys are not allowed
• Values may be duplicated
• Not synchronized
• O(log n) insert, delete, and lookup

Example:

Map<Integer, String> map = new TreeMap<>();

map.put(30, "C");
map.put(10, "A");
map.put(20, "B");

System.out.println(map);

Output:

{10=A, 20=B, 30=C}

Notice that insertion order is not preserved.

The map is sorted by key.

2. TreeSet¶

TreeSet is implemented using a TreeMap.

Internally:

TreeSet

↓

TreeMap

↓

Key -> PRESENT

Exactly like:

HashSet

↓

HashMap

The only difference is:

HashSet → HashMap

TreeSet → TreeMap

3. Class Hierarchy¶

TreeMap¶

Map
 │
SortedMap
 │
NavigableMap
 │
TreeMap

TreeSet¶

Collection
 │
Set
 │
SortedSet
 │
NavigableSet
 │
TreeSet

4. Why Not Binary Search Tree?¶

Interview favorite.

Normal BST:

        50
       /
      40
     /
    30
   /
 20
/
10

Height:

5

Searching:

O(n)

The tree becomes skewed.

Balanced tree:

        30
      /    \
    20      40
   /          \
 10            50

Height:

3

Searching:

O(log n)

5. Red-Black Tree¶

Java uses a self-balancing Red-Black Tree.

Each node has:

Key

Value

Color

Color:

RED

or

BLACK

6. Red-Black Tree Rules¶

Every Red-Black Tree satisfies:

Rule 1¶

Every node is:

RED

or

BLACK

Rule 2¶

Root is always:

BLACK

Rule 3¶

Red node cannot have red children.

RED

↓

RED

❌

Rule 4¶

Every path from root to leaf contains the same number of black nodes.

This keeps the tree balanced.

7. Why Red-Black Trees?¶

Interview question.

Advantages:

• Guaranteed O(log n)
• Fewer rotations than AVL trees
• Excellent for frequent insertions and deletions
• Good balance between lookup and update performance

8. Node Structure¶

Simplified JDK implementation:

static final class Entry<K,V> {

    K key;

    V value;

    Entry<K,V> left;

    Entry<K,V> right;

    Entry<K,V> parent;

    boolean color;
}

Notice:

Unlike HashMap:

next

TreeMap has:

left

right

parent

color

9. Insertion¶

Example:

map.put(20,"A");

map.put(10,"B");

map.put(30,"C");

Tree:

      20
     /  \
   10    30

Easy.

Suppose:

map.put(5,"D");

Now:

      20
     /
   10
   /
  5

The Red-Black Tree may violate balancing rules.

Java performs:

• Recoloring
• Rotations

10. Left Rotation¶

Before:

    10
      \
      20
        \
        30

After left rotation:

      20
     /  \
   10   30

11. Right Rotation¶

Before:

      30
     /
   20
  /
10

After:

      20
     /  \
   10   30

Interview note:

You don't need to memorize every Red-Black insertion case unless you're interviewing for JVM or compiler roles.

You should know:

• Why rotations happen
• What they achieve
• That they preserve sorted order while restoring balance

12. Lookup¶

Example:

map.get(40);

Traversal:

30

↓

40

Each comparison eliminates roughly half the remaining search space.

Complexity:

O(log n)

13. Deletion¶

Deleting a node may violate Red-Black properties.

Java fixes this using:

• Rotations
• Recoloring

Complexity:

O(log n)

14. Ordering¶

Natural ordering:

TreeMap<Integer,String>

Sorted:

1

2

3

4

5

Custom ordering:

Comparator<Integer> reverse =
        Comparator.reverseOrder();

TreeMap<Integer,String> map =
        new TreeMap<>(reverse);

Output:

5

4

3

2

1

15. Comparable vs Comparator¶

Comparable¶

Implemented inside the class.

class Employee
        implements Comparable<Employee> {

    @Override
    public int compareTo(Employee other) {
        return Integer.compare(id, other.id);
    }
}

Defines the natural ordering.

Comparator¶

External ordering.

Comparator<Employee> bySalary =
        Comparator.comparing(Employee::getSalary);

No modification to the class is required.

16. Duplicate Keys¶

Example:

map.put(1,"A");

map.put(1,"B");

Result:

1 → B

TreeMap replaces the existing value.

Exactly like HashMap.

17. Null Keys¶

Interview favorite.

HashMap:

Allows

1 null key

TreeMap:

Null key

↓

NullPointerException

Why?

Natural ordering requires comparing keys.

null.compareTo(...)

is impossible.

Exception: If you provide a custom Comparator that explicitly supports null values, a TreeMap can accept null keys.

18. NavigableMap¶

TreeMap implements:

NavigableMap

Useful methods:

higherKey()

lowerKey()

ceilingKey()

floorKey()

firstKey()

lastKey()

Example:

TreeMap<Integer,String> map = new TreeMap<>();

map.put(10,"A");
map.put(20,"B");
map.put(30,"C");

System.out.println(map.ceilingKey(15));

Output:

20

19. Range Queries¶

HashMap:

Impossible.

TreeMap:

map.subMap(20, true, 50, true);

Returns:

20

30

40

50

This is why TreeMap is useful for:

• Time-series data
• Leaderboards
• Scheduling
• Price ranges

20. TreeSet¶

TreeSet provides:

higher()

lower()

ceiling()

floor()

pollFirst()

pollLast()

Example:

TreeSet<Integer> set = new TreeSet<>();

set.add(10);
set.add(20);
set.add(30);

System.out.println(set.higher(20));

Output:

30

21. Performance Comparison¶

22. TreeSet vs HashSet¶

23. Production Use Cases¶

Use TreeMap when:

• Keys must remain sorted
• You need range searches
• You need nearest-value lookups (floor, ceiling)
• You need ordered iteration

Examples:

• Event scheduling
• Stock prices
• Order books
• Ranking systems
• Calendar applications

Common Interview Questions¶

Q1. Why is TreeMap slower than HashMap?¶

Because TreeMap maintains sorted order using a Red-Black Tree, which requires O(log n) operations instead of average O(1) hashing.

Q2. Why use a Red-Black Tree instead of a BST?¶

A plain BST can become skewed and degrade to O(n). A Red-Black Tree remains balanced, guaranteeing O(log n).

Q3. What is the purpose of rotations?¶

To restore balance after insertions or deletions while preserving the in-order sequence of keys.

Q4. Can TreeMap store duplicate keys?¶

No.

A new value replaces the old one.

Q5. Can TreeSet contain duplicates?¶

No.

Elements compare as equal if compareTo() or the Comparator returns 0.

Q6. Can TreeMap store null keys?¶

Not with natural ordering.

Only with a comparator that explicitly handles null.

Q7. When should you use TreeMap instead of HashMap?¶

When sorted keys or range-based operations are required.

Q8. What is the complexity of higherKey()?¶

O(log n)

Senior Interview Tip¶

One of the most common mistakes is saying:

"TreeMap uses equals() to detect duplicate keys."

This is not entirely correct.

For key uniqueness, TreeMap primarily relies on:

• compareTo() (natural ordering), or
• the supplied Comparator

If the comparison returns 0, the keys are considered the same for map purposes, even if equals() returns false.

Example:

Comparator<String> byLength =
    Comparator.comparingInt(String::length);

TreeMap<String, Integer> map = new TreeMap<>(byLength);

map.put("cat", 1);
map.put("dog", 2);

System.out.println(map);

Output:

{cat=2}

Both strings have length 3, so the comparator returns 0. "dog" replaces "cat".

This is why the comparator should be consistent with equals() unless you intentionally want different behavior.

Key Takeaways¶

• TreeMap is implemented using a Red-Black Tree.
• It guarantees O(log n) insertion, lookup, and deletion.
• Keys remain sorted automatically.
• TreeSet is implemented on top of TreeMap.
• Balancing is maintained through rotations and recoloring.
• NavigableMap and NavigableSet provide powerful range and nearest-neighbor operations.
• compareTo()/Comparator determine ordering and key uniqueness.

Next: Part 7 — Queue & Deque Deep Dive¶

We'll cover:

• Queue vs Deque
• PriorityQueue internals (binary heap)
• ArrayDeque implementation
• Why ArrayDeque is preferred over Stack
• BlockingQueue overview
• Producer–Consumer pattern
• BFS algorithms
• Scheduling systems
• Interview questions and production use cases