<p>This is another very frequently asked <strong><a href="https://dineshonjava.com/core-java-baby-step-to-be-best-java-ian/">Java</a> </strong>Developer <strong><a href="https://dineshonjava.com/core-java-interview-questions/">Interview Questions</a></strong> of Internal Working of <strong><a href="https://dineshonjava.com/treemap-class-in-collection-framework/">TreeMap in Java</a></strong>. How TreeMap works and what is an internal implementation of TreeMap. In our previous articles, we have already discussed other popular<strong><a href="https://dineshonjava.com/core-java-interview-questions/"> java interview questions</a></strong> such as the <strong><a href="https://dineshonjava.com/internal-working-of-hashmap-in-java/">internal working of HashMap</a></strong> and <strong><a href="https://dineshonjava.com/internal-working-of-linkedhashmap-in-java/">internal working of LinkedHashMap</a></strong>. Also, we have discussed, what is the <strong><a href="https://dineshonjava.com/difference-between-treemap-vs-hashmap/">difference between HashMap and TreeMap</a></strong>. In this article, we will discuss the Internal Working of TreeMap in Java.</p>
<blockquote><p><strong>LinkedList Algorithms Interview Questions</strong></p>
<p><strong><a href="https://dineshonjava.com/find-and-break-a-loop-in-a-linked-list/">Find and Break a Loop in a Linked list</a></strong><br />
<strong><a href="https://dineshonjava.com/how-to-detect-loop-in-a-linked-list/">How to Detect loop in a linked list</a></strong><br />
<strong><a href="https://dineshonjava.com/nth-node-from-the-end-of-a-singly-linked-list/">Find the nth node from the end of a singly linked list</a></strong><br />
<strong><a href="https://dineshonjava.com/find-the-middle-element-in-a-linked-list/">Find the middle element in a linked list</a></strong><br />
<strong><a href="https://dineshonjava.com/reverse-linked-list/">How to Reverse linked list in Java</a></strong><br />
<strong><a href="https://dineshonjava.com/delete-given-node-from-singly-linked-list/">Delete given node from a singly linked list</a></strong><br />
<strong><a href="https://dineshonjava.com/remove-duplicates-from-the-unsorted-singly-linked-list/">Remove Duplicates from the Unsorted Singly Linked list</a></strong><br />
<strong><a href="https://dineshonjava.com/singly-linked-list-is-palindrome/">The singly linked list is palindrome without extra space</a></strong></p></blockquote>
<h2>TreeMap in Java</h2>
<p>The TreeMap is used to implement <strong><a href="https://dineshonjava.com/map-interface-in-collection/">Map interface</a></strong> and <em>NavigableMap</em> along with the Abstract Class. <em>TreeMap</em> does not use hashing for storing key unlike the <em>HashMap</em> and <em>LinkedHashMap</em> use hashing for storing the key. <em>HashMap</em> and <em>LinkedHashMap</em> use array data structure to store nodes but the <em>TreeMap</em> uses a data structure called Red-Black tree. Also, all its elements store in the <em>TreeMap</em> are sorted by key. <em>TreeMap</em> performs sorting in natural order on its key, it also allows you to use <strong><a href="https://dineshonjava.com/java-comparable-and-comparator/#.VGtB4jSUeLp">Comparator</a></strong> for custom sorting implementation. We can provide <em>Comparator</em> at map creation time, depending on which constructor is used. Let&#8217;s see the following:</p>
<ul>
<li><strong>TreeMap():</strong> This default constructor constructs an empty <em>TreeMap</em> that will be sorted by using the natural order of its keys.</li>
<li><strong>TreeMap(Comparator comp):</strong> This is an argument constructor and it takes <em>Comparator</em> object to constructs an empty tree-based map. It will be sorted by using the <em>Comparator</em> comp.</li>
<li><strong>TreeMap(Map map):</strong> It creates a TreeMap with the entries from a map, which will be sorted by using the natural order of the keys.</li>
<li><strong>TreeMap(SortedMap sortedMap):</strong> It also initializes a <em>TreeMap</em> with the entries from sortedMap, which will be sorted in the same order as sortedMap.</li>
</ul>
<p>As we have seen various overloaded constructors of a <em>TreeMap</em>. Let&#8217;s see the performance factor of the <em>TreeMap</em> as the below:</p>
<h2>Performance of TreeMap</h2>
<p>Performance wise <em>TreeMap</em> is slow if you will compare with <em>HashMap</em> and <em>LinkedHashMap</em>. The <em>TreeMap</em> provides guaranteed log(n) time complexity for the methods such as <em>containsKey(), get(), put() and remove().</em></p>
<p>Also, a <em>TreeMap</em> 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:</p>
<pre>SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...)); 
</pre>
<p>Let&#8217;s discuss the internal structure of a <em>TreeMap</em>.</p>
<h2>Internal Structure of TreeMap</h2>
<p><em>TreeMap</em> 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&#8217;s see the following diagram:</p>
<p><img class="aligncenter size-full wp-image-4304" src="https://dineshonjava.com/wp-content/uploads/2018/10/Treemap3-5.png" alt="Treemap Node" width="691" height="442" /><br />
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:</p>
<ol>
<li>The <em>left</em> element will always be logically less than the <em>parent</em> element.</li>
<li>The <em>right</em> element will always be logically greater than OR equal to a <em>parent</em> element</li>
<li>The logical comparison of Objects is done by natural order i.e. those object who implement <em>Comparable</em> interface and override <em>compareTo(Object obj)</em> method. Based on the return value,</li>
</ol>
<p>Let&#8217;s see the following use of the <em>compareTo()</em> method:</p>
<ul>
<li>If obj1.compareTo(obj2) returns a negative number, then obj1 is logically less than obj2.</li>
<li>If obj1.compareTo(obj2) returns positive number then obj1 is logically greater than obj2</li>
<li>If obj1.compareTo(obj2) returns zero, then obj1 is equal to obj2.</li>
</ul>
<p>As we have discussed, TreeMap is working based on the Red-Black tree.</p>
<h2>Red Black tree</h2>
<p>In this article, I am not going to explain the Red Black algorithm in details, let&#8217;s see the pseudo code of Red Black algorithm in order to understand the internal implementation like the following:</p>
<ul>
<li>As the name of the algorithm suggests, a colour of every node in the tree is either red or black.</li>
<li>Root node must be Black in color.</li>
<li>A red node can not have a red colour neighbor node.</li>
<li>All paths from a root node to the null should consist the same number of black nodes.</li>
</ul>
<h2>Internal Working of TreeMap in Java</h2>
<p>Now, we will discuss an example and see how does TreeMap work internally.</p>
<pre>/** 
 * 
 */ 
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"); 
	} 
 
} 
 
</pre>
<p>Let&#8217;s see Key class:</p>
<pre> 
/** 
 * 
 */ 
package com.dineshonjava.algo.map; 
 
/** 
 * @author Dinesh.Rajput 
 * 
 */ 
public class Key implements Comparable<Key>{ 
	 
	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); 
	} 
	 
} 
</pre>
<p>As you can see in the above Key class, I didn&#8217;t implement hashCode() and equals() method becuase TreeMap does not use hashing.</p>
<h3>Let&#8217;s understand step by step.</h3>
<p><strong>Step 1:</strong> Initially when we create a TreeMap object as</p>
<pre>Map<;Key, String>; treemap = new TreeMap<;>;(); 
</pre>
<p>There are no elements in it. Let&#8217;s add the first element on it.</p>
<p><strong>Step 2: Adding the first element into TreeMap</strong></p>
<pre>treemap.put(new Key("Anamika"), "Anamika"); 
</pre>
<p>So {&#8220;Anamika&#8221;} is the first key object being inserted as key. This element will be root node for tree and structure for TreeMap becomes as below.</p>
<p><img class="aligncenter wp-image-4305 size-full" src="https://dineshonjava.com/wp-content/uploads/2018/10/FirstIntegerInserted.png" alt="Internal Working of TreeMap in Java" width="316" height="219" /></p>
<p><strong>Step 3: Adding the second element into TreeMap</strong></p>
<pre>treemap.put(new Key("Rushika"), "Rushika"); 
</pre>
<p>Now, {&#8220;Rushika&#8221;} is logically greater than {&#8220;Anamika&#8221;} and hence according to our rules,</p>
<ul>
<li>{&#8220;Rushika&#8221;} will be placed to the right of {&#8220;Anamika&#8221;}.</li>
<li>{&#8220;Anamika&#8221;} will be a parent of {&#8220;Rushika&#8221;}.</li>
</ul>
<p>After inserting this element, the structure for TreeMap becomes as below.</p>
<p><img class="aligncenter size-full wp-image-4306" src="https://dineshonjava.com/wp-content/uploads/2018/10/SecondIntegerInserted.png" alt="SecondElementInserted" width="742" height="372" /></p>
<p><strong>Step 4: Adding third element into TreeMap</strong></p>
<pre>treemap.put(new Key("Dinesh"), "Dinesh");</pre>
<p>So {&#8220;Dinesh&#8221;} is the first key object being inserted as key. This element will be root node for tree and structure for TreeMap becomes as below.</p>
<p><img class="aligncenter size-full wp-image-4307" src="https://dineshonjava.com/wp-content/uploads/2018/10/ThirdObjectInserted-1.png" alt="ThirdElementInserted" width="1106" height="372" /></p>
<p>As you can see in the above diagram, this element {&#8220;Dinesh&#8221;} 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.</p>
<ul>
<li>{&#8220;Anamika&#8221;} will be to the left of {&#8220;Dinesh&#8221;}</li>
<li>{&#8220;Rushika&#8221;} will be to the right of {&#8220;Dinesh&#8221;}</li>
</ul>
<p><strong>Step 5: Adding the third element into TreeMap</strong></p>
<pre>treemap.put(new Key("Arnav"), "Arnav");</pre>
<p>So {&#8220;Arnav&#8221;} is the first key object being inserted as key. After adding this element, a structure for TreeMap becomes as below.</p>
<p><img class="aligncenter size-full wp-image-4308" src="https://dineshonjava.com/wp-content/uploads/2018/10/FourthObjecctInserted.png" alt="FourthObjecctInserted" width="1106" height="555" /></p>
<p>As you can see in the above diagram of the TreeMap, all elements are as below:</p>
<ul>
<li>{&#8220;Anamika&#8221;} will be to the left of {&#8220;Dinesh&#8221;}</li>
<li>{&#8220;Arnav&#8221;} will be to right of {&#8220;Dinesh&#8221;}</li>
<li>{&#8220;Rushika&#8221;} will be to right of {&#8220;Anamika&#8221;}</li>
</ul>
<p>Hope this article is able to give much information about the internal working of <em>TreeMap</em> in Java.</p>
<p>Happy Learning with DineshonJava.</p>
<div align="center"><iframe style="width: 120px; height: 240px;" src="//ws-in.amazon-adsystem.com/widgets/q?ServiceVersion=20070822&;OneJS=1&;Operation=GetAdHtml&;MarketPlace=IN&;source=ac&;ref=qf_sp_asin_til&;ad_type=product_link&;tracking_id=dineshonjav06-21&;marketplace=amazon&;region=IN&;placement=1788299450&;asins=1788299450&;linkId=05b0146b0a85f4472697901e353dc276&;show_border=true&;link_opens_in_new_window=true&;price_color=333333&;title_color=0066c0&;bg_color=ffffff" frameborder="0" marginwidth="0" marginheight="0" scrolling="no"><br />
</iframe></div>
<div align="center">
<iframe width="560" height="315" src="https://www.youtube.com/embed/787IEebrYXM" frameborder="0" allow="autoplay; encrypted-media" allowfullscreen></iframe></div>
<div class="wp-post-navigation"> 
									 <div class="wp-post-navigation-pre"> 
									 <a href="https://dineshonjava.com/internal-working-of-linkedhashmap-in-java/">Previous</a> 
									 </div> 
									 <div class="wp-post-navigation-next"> 
									 <a href="https://dineshonjava.com/implement-lru-cache-algorithm-in-java/">Next</a> 
									 </div> 
									</div>
<script type="text/javascript">
jQuery(document).ready(function($) {
 $.post('https://dineshonjava.com/wp-admin/admin-ajax.php', {action: 'mts_view_count', id: '4303'});
});
</script>
Strategy Design Patterns We can easily create a strategy design pattern using lambda. To implement…
Decorator Pattern A decorator pattern allows a user to add new functionality to an existing…
Delegating pattern In software engineering, the delegation pattern is an object-oriented design pattern that allows…
Technology has emerged a lot in the last decade, and now we have artificial intelligence;…
Managing a database is becoming increasingly complex now due to the vast amount of data…
Overview In this article, we will explore Spring Scheduler how we could use it by…