TreeMap Internal Working in Java with Examples

TreeMap is one of the most important Map implementations in Java Collections Framework. Unlike HashMap, which uses hashing internally, TreeMap stores data in a sorted order using a self-balancing Red-Black Tree.

TreeMap is frequently asked in Java interviews because understanding its internal implementation helps developers choose the correct collection based on requirements such as sorting, searching, and performance.

What is TreeMap?

TreeMap is a class that implements the NavigableMap interface and stores data in sorted key order. By default, sorting is performed according to the natural ordering of keys.

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

map.put(103, "Spring");
map.put(101, "Java");
map.put(102, "Hibernate");

System.out.println(map);

Output

{101=Java, 102=Hibernate, 103=Spring}

Notice that the entries are automatically sorted by key.

Important Characteristics of TreeMap

• Stores key-value pairs.
• Maintains ascending sorted order of keys.
• Does not allow null keys.
• Allows multiple null values.
• Uses Red-Black Tree internally.
• Not synchronized.

Internal Structure of TreeMap

TreeMap internally uses a Red-Black Tree. A Red-Black Tree is a self-balancing binary search tree that ensures operations remain efficient even when large amounts of data are stored.

A simplified tree structure:

           50
         /    \
       25      75
      / \     / \
    10  35  60  90

Every insertion ensures the tree remains balanced.

Why Does TreeMap Use a Red-Black Tree?

If a normal binary search tree becomes unbalanced, search operations can become slow. The Red-Black Tree automatically balances itself to maintain efficient performance.

This guarantees that insertion, deletion, and searching operations remain fast.

How put() Works Internally

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

map.put(50, "A");
map.put(30, "B");
map.put(70, "C");

When put() is called:

1. The root node is checked.
2. The key is compared with existing keys.
3. The correct position is located.
4. A new node is inserted.
5. The Red-Black Tree balancing algorithm runs.

How get() Works Internally

String value = map.get(30);

TreeMap performs:

1. Start from root node.
2. Compare required key with current node.
3. Move left or right branch.
4. Repeat until key is found.

Because the tree stays balanced, searching remains efficient.

Natural Sorting

TreeMap automatically sorts elements using natural ordering.

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

map.put(5, "Five");
map.put(1, "One");
map.put(3, "Three");

System.out.println(map);

Output

{1=One, 3=Three, 5=Five}

Custom Sorting Using Comparator

You can provide a custom Comparator to change the sorting behaviour.

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

map.put(1, "Java");
map.put(2, "Spring");
map.put(3, "Kafka");

System.out.println(map);

Output

{3=Kafka, 2=Spring, 1=Java}

Null Key Behaviour

Unlike HashMap, TreeMap does not allow null keys.

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

map.put(null, "Java");

Output

Exception in thread "main"
java.lang.NullPointerException

TreeMap requires key comparisons and cannot compare null values.

TreeMap Methods Frequently Used

firstKey()

map.firstKey();

Returns the smallest key.

lastKey()

map.lastKey();

Returns the largest key.

higherKey()

map.higherKey(20);

Returns the next higher key.

lowerKey()

map.lowerKey(20);

Returns the previous lower key.

Internal Example

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

employees.put(103, "Alex");
employees.put(101, "John");
employees.put(102, "David");

System.out.println(employees);

Output

{101=John, 102=David, 103=Alex}

Notice that entries are automatically sorted.

Time Complexity

Operation	Complexity
put()	O(log n)
get()	O(log n)
remove()	O(log n)

TreeMap vs HashMap

Feature	HashMap	TreeMap
Ordering	No	Sorted
Internal Structure	Hash Table	Red-Black Tree
Null Keys	Allowed	Not Allowed
Search Time	O(1)	O(log n)

Common Interview Questions

What data structure does TreeMap use internally?

TreeMap uses a Red-Black Tree internally.

Is TreeMap sorted?

Yes. TreeMap automatically stores entries in sorted order based on key values.

Can TreeMap contain null keys?

No. TreeMap does not allow null keys.

Can TreeMap contain null values?

Yes. Multiple null values are allowed.

When should TreeMap be used?

Use TreeMap when data must always remain sorted.

Frequently Asked Questions (FAQ)

Which is faster: HashMap or TreeMap?

HashMap is generally faster because it provides average O(1) lookup performance. TreeMap operations require O(log n) time.

What is the advantage of TreeMap?

Its biggest advantage is that it always maintains sorted data.

Can TreeMap sort custom objects?

Yes. Either implement Comparable or provide a Comparator.

Is TreeMap thread-safe?

No. TreeMap is not thread-safe.

Keywords

TreeMap Internal Working, TreeMap Interview Questions, Java TreeMap Tutorial, TreeMap Red Black Tree, TreeMap Example Java, TreeMap vs HashMap, TreeMap Time Complexity, Java Collections Framework, Sorted Map in Java, TreeMap Comparator Example, TreeMap Natural Ordering, TreeMap Internal Architecture, Java Collections Interview Questions, TreeMap Null Key, Core Java Collections