TreeMap in Java

Before we jump into TreeMap, let us first look into Tree Data Structure.

Screen Shot 2017-03-14 at 10.41.37 PM

The basic building block for the tree is the node. Tree is nothing but hierarchial ordering of nodes. Some of the basic definitions are defined below:

Root:The top node in a tree. In the above tree structure “A” is the root.
Parent:The node which is predecessor of any node.In other words the node which has child node(s).In the above tree structure “D” is the parent for “E”,”F” and “G”.
Child:The node which is descendant of any node. In a tree, all the nodes except root are child nodes.In the above tree structure  “E”,”F” and “G” are the children of “D”.
Siblings:A group of nodes with the same parent.In the above tree structure  “E”,”F” and “G” are the siblings.
Leaf:A node with no children.In the above tree structure  “C”,”E”,”F”, “G”,”H” and “I” are the leaf nodes.

Now let us know what is a Binary Tree?

Screen Shot 2017-03-14 at 10.38.34 PM

The above is an example of binary tree.Binary tree is a special tree where each node can have no more than two children.

Now let us know what is a Binary Search Tree(BST)?

Screen Shot 2017-03-14 at 10.39.27 PM

The above is an example of Binary Search Tree. In this case, a node’s left child must have a value less than its parent’s value and the node’s right child must have a value greater than  or equal to its parent value.

Balanced Binary Search Tree(Balanced BST)

Balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically.

Screen Shot 2017-03-18 at 6.54.41 PM

Advantages of Balanced BST:

Most operations on a BST take time proportional to the height of the tree, so it is desirable to keep the height small. For normal BST, the worst case for search, add and remove operations is O(n), whereas in case of Binary BST it is O(log n).

Self-balancing binary trees solve this problem by performing transformations on the tree at key times, in order to reduce the height. Although a certain overhead is involved, it is justified in the long run by ensuring fast execution of later operations.

Implementations of Balanced BST

Following are popular Balanced Binary Search tree implementations.

  1. 2-3 tree
  2. AA tree
  3. AVL tree
  4. Red-black tree
  5. Scapegoat tree
  6. Splay tree
  7. Treap

Now let us come to our main topic i.e., TreeMap.TreeMap is a Red-Black tree based implementation of Map.

Following are the properties of Red-black tree.

  1. Every node is either red or black.
  2. Every leaf is a NIL node, and is colored black.
  3. If a node is red, then both its children are black. That is a red node can’t have a red child node.
  4. Every simple path from a node to a descendant leaf contains the same number of black nodes.
  5. The root node is always black

Screen Shot 2017-03-18 at 7.14.03 PM

We will not go in deep into Red-Black Tree as it is based on some complex algorithms and in any case these internal details are not needed for us.

In TreeMap the entries(key-value pairs) are sorted based on the keys.

The objects to be used as key in the TreeMap should implement Comparable interface.Otherwise a Comparator which can compare the keys needs to be passed an argument while creating the TreeMap.

Let us take the example of Employee. In this case, the natural ordering of the Employee is by Id. We have also created two Comparators SalaryComparator and NameComparator to sort Employees by Salary and Name respectively.

Employee Class which implements Comparable

package com.comparable.example;

public class Employee implements Comparable{

private String name;
private Long salary;
private Long id;
public String getName() {
return name;
public void setName(String name) { = name;
public Long getSalary() {
return salary;
public Employee(String name, Long salary, Long id) { = name;
this.salary = salary; = id;
public String toString() {
return “Employee [name=” + name + “, salary=” + salary + “, id=” + id
+ “]”;
public void setSalary(Long salary) {
this.salary = salary;
public Long getId() {
return id;
public void setId(Long id) { = id;
public int compareTo(Employee employee) {
return this.getId().compareTo(employee.getId());



package com.comparator.example;

import java.util.Comparator;

import com.comparable.example.Employee;

public class SalaryComparator implements Comparator{

public int compare(Employee emp1, Employee emp2) {
return emp1.getSalary().compareTo(emp2.getSalary());



package com.comparator.example;

import java.util.Comparator;

import com.comparable.example.Employee;

public class NameComparator implements Comparator{

public int compare(Employee emp1, Employee emp2) {
return emp1.getName().compareTo(emp2.getName());


TestEmployee class

package com.comparable.example;

import java.util.Map;

import java.util.TreeMap;

import com.comparator.example.NameComparator;

import com.comparator.example.SalaryComparator;

public class TestEmployee {

public static void main(String[] args) {

Map<Employee,String> treeMap = new TreeMap<Employee,String>();

Map<Employee,String> salaryBasedTreeMap = new TreeMap<Employee,String>(new SalaryComparator());

Map<Employee,String> nameBasedTreeMap = new TreeMap<Employee,String>(new NameComparator());

Employee emp1 = new Employee(“Gyan”, 1000000L, 1L);

treeMap.put(emp1, “Bhubaneswar”);

salaryBasedTreeMap.put(emp1, “Bhubaneswar”);

nameBasedTreeMap.put(emp1, “Bhubaneswar”);

Employee emp2 = new Employee(“Praveen”, 1500000L, 2L);

treeMap.put(emp2, “New Delhi”);

salaryBasedTreeMap.put(emp2, “New Delhi”);

nameBasedTreeMap.put(emp2, “New Delhi”);

Employee emp3 = new Employee(“Rochit”, 800000L, 4L);

treeMap.put(emp3, “Bangalore”);

salaryBasedTreeMap.put(emp3, “Bangalore”);

nameBasedTreeMap.put(emp3, “Bangalore”);

Employee emp4 = new Employee(“Vivek”, 12000000L, 3L);

treeMap.put(emp4, “Calcutta”);

salaryBasedTreeMap.put(emp4, “Calcutta”);

nameBasedTreeMap.put(emp4, “Calcutta”);

Employee emp5 = new Employee(“Prabhakar”, 1800000L, 5L);

treeMap.put(emp5, “Mangalore”);

salaryBasedTreeMap.put(emp5, “Mangalore”);

nameBasedTreeMap.put(emp5, “Mangalore”);

Employee emp6 = new Employee(“Sudeep”, 1600000L, 6L);

treeMap.put(emp6, “Chennai”);

salaryBasedTreeMap.put(emp6, “Chennai”);

nameBasedTreeMap.put(emp6, “Chennai”);

System.out.println(“Natural Ordering by Id:”+treeMap);

System.out.println(“Ordering by Salary:”+salaryBasedTreeMap);

System.out.println(“Ordering by Name:”+nameBasedTreeMap);




Natural Ordering by Id:{Employee [name=Gyan, salary=1000000, id=1]=Bhubaneswar, Employee [name=Praveen, salary=1500000, id=2]=New Delhi, Employee [name=Vivek, salary=12000000, id=3]=Calcutta, Employee [name=Rochit, salary=800000, id=4]=Bangalore, Employee [name=Prabhakar, salary=1800000, id=5]=Mangalore, Employee [name=Sudeep, salary=1600000, id=6]=Chennai}

Ordering by Salary:{Employee [name=Rochit, salary=800000, id=4]=Bangalore, Employee [name=Gyan, salary=1000000, id=1]=Bhubaneswar, Employee [name=Praveen, salary=1500000, id=2]=New Delhi, Employee [name=Sudeep, salary=1600000, id=6]=Chennai, Employee [name=Prabhakar, salary=1800000, id=5]=Mangalore, Employee [name=Vivek, salary=12000000, id=3]=Calcutta}

Ordering by Name:{Employee [name=Gyan, salary=1000000, id=1]=Bhubaneswar, Employee [name=Prabhakar, salary=1800000, id=5]=Mangalore, Employee [name=Praveen, salary=1500000, id=2]=New Delhi, Employee [name=Rochit, salary=800000, id=4]=Bangalore, Employee [name=Sudeep, salary=1600000, id=6]=Chennai, Employee [name=Vivek, salary=12000000, id=3]=Calcutta}

Leave a Reply

Your email address will not be published. Required fields are marked *