Internal Working of TreeMap in Java

This is another very frequently asked Java Developer Interview Questions of Internal Working of TreeMap in Java. How TreeMap works and what is an internal implementation of TreeMap. In our previous articles, we have already discussed other popular java interview questions such as the internal working of HashMap and internal working of LinkedHashMap. Also, we have discussed, what is the difference between HashMap and TreeMap. In this article, we will discuss the Internal Working of TreeMap in Java.

LinkedList Algorithms Interview Questions

Find and Break a Loop in a Linked list
How to Detect loop in a linked list
Find the nth node from the end of a singly linked list
Find the middle element in a linked list
How to Reverse linked list in Java
Delete given node from a singly linked list
Remove Duplicates from the Unsorted Singly Linked list
The singly linked list is palindrome without extra space

TreeMap in Java

The TreeMap is used to implement Map interface and NavigableMap along with the Abstract Class. TreeMap does not use hashing for storing key unlike the HashMap and LinkedHashMap use hashing for storing the key. HashMap and LinkedHashMap use array data structure to store nodes but the TreeMap uses a data structure called Red-Black tree. Also, all its elements store in the TreeMap are sorted by key. TreeMap performs sorting in natural order on its key, it also allows you to use Comparator for custom sorting implementation. We can provide Comparator at map creation time, depending on which constructor is used. Let’s see the following:

TreeMap(): This default constructor constructs an empty TreeMap that will be sorted by using the natural order of its keys.
TreeMap(Comparator comp): This is an argument constructor and it takes Comparator object to constructs an empty tree-based map. It will be sorted by using the Comparator comp.
TreeMap(Map map): It creates a TreeMap with the entries from a map, which will be sorted by using the natural order of the keys.
TreeMap(SortedMap sortedMap): It also initializes a TreeMap with the entries from sortedMap, which will be sorted in the same order as sortedMap.

As we have seen various overloaded constructors of a TreeMap. Let’s see the performance factor of the TreeMap as the below:

Performance of TreeMap

Performance wise TreeMap is slow if you will compare with HashMap and LinkedHashMap. The TreeMap provides guaranteed log(n) time complexity for the methods such as containsKey(), get(), put() and remove().

Also, a TreeMap is fail-fast in nature that means it is not synchronized and that is why is not thread-safe. You can make it thread-safe for multithreaded environments as the following:

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

Let’s discuss the internal structure of a TreeMap.

Internal Structure of TreeMap

TreeMap is based on tree data structure as its name suggested. As we know that, in a tree, each node has three references its parent, right and left element. Let’s see the following diagram:

Treemap Node
As you can see in the above diagram, there are three references in the node such as a parent, right and left element with the following properties:

The left element will always be logically less than the parent element.
The right element will always be logically greater than OR equal to a parent element
The logical comparison of Objects is done by natural order i.e. those object who implement Comparable interface and override compareTo(Object obj) method. Based on the return value,

Let’s see the following use of the compareTo() method:

If obj1.compareTo(obj2) returns a negative number, then obj1 is logically less than obj2.
If obj1.compareTo(obj2) returns positive number then obj1 is logically greater than obj2
If obj1.compareTo(obj2) returns zero, then obj1 is equal to obj2.

As we have discussed, TreeMap is working based on the Red-Black tree.

Red Black tree

In this article, I am not going to explain the Red Black algorithm in details, let’s see the pseudo code of Red Black algorithm in order to understand the internal implementation like the following:

As the name of the algorithm suggests, a colour of every node in the tree is either red or black.
Root node must be Black in color.
A red node can not have a red colour neighbor node.
All paths from a root node to the null should consist the same number of black nodes.

Internal Working of TreeMap in Java

Now, we will discuss an example and see how does TreeMap work internally.

/**
 * 
 */
package com.dineshonjava.algo.map;

import java.util.Map;
import java.util.TreeMap;

/**
 * @author Dinesh.Rajput
 *
 */
public class TreeMapTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Map<Key, String> treemap = new TreeMap<>();
                treemap.put(new Key("Anamika"), "Anamika");
		treemap.put(new Key("Rushika"), "Rushika");
		treemap.put(new Key("Dinesh"), "Dinesh");
		treemap.put(new Key("Arnav"), "Arnav");
	}

}

Let’s see Key class:

/**
 * 
 */
package com.dineshonjava.algo.map;

/**
 * @author Dinesh.Rajput
 *
 */
public class Key implements Comparable{
	
	final int data = 112;
	private String key;
	
	public Key(String key) {
		super();
		this.key = key;
	}
	
	@Override
	public int compareTo(Key obj) {
		return key.compareTo(obj.key);
	}
	
}

As you can see in the above Key class, I didn’t implement hashCode() and equals() method becuase TreeMap does not use hashing.

Let’s understand step by step.

Step 1: Initially when we create a TreeMap object as

Map<Key, String> treemap = new TreeMap<>();

There are no elements in it. Let’s add the first element on it.

Step 2: Adding the first element into TreeMap

treemap.put(new Key("Anamika"), "Anamika");

So {“Anamika”} is the first key object being inserted as key. This element will be root node for tree and structure for TreeMap becomes as below.

Internal Working of TreeMap in Java

Step 3: Adding the second element into TreeMap

treemap.put(new Key("Rushika"), "Rushika");

Now, {“Rushika”} is logically greater than {“Anamika”} and hence according to our rules,

{“Rushika”} will be placed to the right of {“Anamika”}.
{“Anamika”} will be a parent of {“Rushika”}.

After inserting this element, the structure for TreeMap becomes as below.

SecondElementInserted

Step 4: Adding third element into TreeMap

treemap.put(new Key("Dinesh"), "Dinesh");

So {“Dinesh”} is the first key object being inserted as key. This element will be root node for tree and structure for TreeMap becomes as below.

ThirdElementInserted

As you can see in the above diagram, this element {“Dinesh”} is the root node for a tree. As we have discussed above properties and rules of the Red-Black tree, the Red-Black tree implementation will give us sorted order from left to right. So according to diagram elements of a tree become as below.