How to sort HashMap in java by keys and values

HashMap does not preserve order of element but what if you want to sort it by keys or values. In this post, we will see how to sort HashMap by keys or values.

Sorting by Keys: 

Sorting by keys can be easily done using TreeMap. You just need to pass HashMap to the constructor of TreeMap.
TreeMap map=new TreeMap(Map hm);

Sorting by values:

We can use Comparator to sort it by values.

Sorting by Keys example :

Create Country.java as below. It should implement Comparable interface
package org.arpit.java2blog;  
public class Country implements Comparable {  
  
 String name;  
 long population;  
   
 public Country(String name, long population) {  
  super();  
  this.name = name;  
  this.population = population;  
 }  
 public String getName() {  
  return name;  
 }  
 public void setName(String name) {  
  this.name = name;  
 }  
 public long getPopulation() {  
  return population;  
 }  
 public void setPopulation(long population) {  
  this.population = population;  
 }
@Override
public int compareTo(Object o) {
    Country country=(Country) o;
 return this.getName().compareTo(country.getName());
}  
       
}  

Create TreeMapCompMain.java as below:
package org.arpit.java2blog;

import java.util.HashMap;
import java.util.Iterator;
import java.util.TreeMap;

public class TreeMapCompMain {

 public static void main(String[] args)
 {
  Country india=new Country("India",1000);  
        Country japan=new Country("Japan",10000);  
            
        Country france=new Country("France",2000);  
        Country russia=new Country("Russia",20000);  
            
        HashMap<Country, String> countryCapitalMap=new HashMap<Country,String>();  
        countryCapitalMap.put(india,"Delhi");  
        countryCapitalMap.put(japan,"Tokyo");  
        countryCapitalMap.put(france,"Paris");  
        countryCapitalMap.put(russia,"Moscow");  
        
        System.out.println("Sorting HashMap by passing it to TreeMap constructor");
        TreeMap<Country,String> sortedTreeMapCountryCapital=new  TreeMap<Country,String> (countryCapitalMap);
        Iterator<Country> countryCapitalIter=sortedTreeMapCountryCapital.keySet().iterator();//put debug point at this line  
        while(countryCapitalIter.hasNext())  
        {  
            Country countryObj=countryCapitalIter.next();  
            String capital=countryCapitalMap.get(countryObj);  
            System.out.println(countryObj.getName()+"----"+capital);  
            }  
        }  

}

When you run program, you will get below output:
Sorting HashMap by passing it to TreeMap constructor
France----Paris
India----Delhi
Japan----Tokyo
Russia----Moscow

Sorting by values example: 

Here we will sort HashMap by its values. Here I am taking HashMap <String,String> to make example simpler.
Example:
package org.arpit.java2blog;

import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.ArrayList;
import java.util.List;
import java.util.Map.Entry;
import java.util.Set;

public class HashMapMain {

 public static void main(String args[]) {
  // HashMap with Country name as key and capital as value
  // HashMap stores elements in key value pairs
  HashMap<String, String> countryCapitalMap = new HashMap<String, String>();

  countryCapitalMap.put("Japan", "Tokyo");
  countryCapitalMap.put("France", "Paris");
  countryCapitalMap.put("Russia", "Moscow");
  countryCapitalMap.put("India", "Delhi");

  System.out.println("-----------------------------");
  // Iterating HashMap Using keySet() and for each loop
  System.out.println("Before Sorting");
  System.out.println("-----------------------------");
  for (String countryKey : countryCapitalMap.keySet()) {
   System.out.println("Country:" + countryKey + " and  Capital:" + countryCapitalMap.get(countryKey));

  }
  
  Set<Entry<String, String>> countryCapitalEntrySet=countryCapitalMap.entrySet();
  
  List<Entry<String, String>> entryList=new ArrayList<Entry<String, String>>(countryCapitalEntrySet);
  
  Collections.sort(entryList,new Comparator<Entry<String,String>>() {

   @Override
   public int compare(Entry<String,String> o1, Entry<String,String> o2) {
    return o1.getValue().compareTo(o2.getValue());
   }
  });
  System.out.println("-----------------------------");
     
  // Using LinkedHashMop to keep entries in sorted order
  LinkedHashMap<String,String> sortedHashMap=new LinkedHashMap<String,String>();
  for (Entry<String,String> entry:entryList) {
   sortedHashMap.put(entry.getKey(), entry.getValue());
  }
  
  System.out.println("After Sorting");
  System.out.println("-----------------------------");
  // Iterating sortedHashMap Using keySet() and for each loop
  
  for (String countryKey : sortedHashMap.keySet()) {
   System.out.println("Country:" + countryKey + " and  Capital:" + sortedHashMap.get(countryKey));

  }
 }
}
When you run above program, you will get below output
-----------------------------
Before Sorting
-----------------------------
Country:France and  Capital:Paris
Country:Russia and  Capital:Moscow
Country:Japan and  Capital:Tokyo
Country:India and  Capital:Delhi
-----------------------------
After Sorting
-----------------------------
Country:India and  Capital:Delhi
Country:Russia and  Capital:Moscow
Country:France and  Capital:Paris
Country:Japan and  Capital:Tokyo

Explanation:

  • Extract key set from HashMap using keySet() method.
  • Create ArrayList from above set
  • Sort above ArrayList using Comparator
  • Create LinkedHashMap from Sorted list

LinkedHashSet in java with example

In this post, we will see about LinkedHashSet in java. LinkedHashSet is same as HashSet except that it maintains insertion order.

Some points about LinkedHashSet
  1. LinkedHashSet implements Set interface and extends HashSet class.
  2. LinkedHashSet maintains insertion order, so when you will be able to access elements in the order they were inserted like ArrayList.

Example:

LinkedHashSetMain.java
package org.arpit.java2blog;

import java.util.LinkedHashSet;

public class LinkedHashSetMain {

 public static void main(String args[])
 {
 // LinkedHashSet with Country
 // LinkedHashSet maintains insertion order  
  LinkedHashSet&lt;String&gt; countryHashSet=new LinkedHashSet&lt;String&gt;();
  countryHashSet.add("India");
  countryHashSet.add("Japan");
  countryHashSet.add("France");
  countryHashSet.add("Russia");
  countryHashSet.add("India");
  countryHashSet.add("France");
  countryHashSet.add("United Kingdom");

  System.out.println("-----------------------------");
 
  System.out.println("Iterating LinkedHashSet");
  System.out.println("-----------------------------");
  for (String country:countryHashSet) {
   System.out.println(country);

  }
  System.out.println("-----------------------------");
}

}

When you run above program, you will get below output:
-----------------------------
Iterating LinkedHashSet
-----------------------------
India
Japan
France
Russia
United Kingdom
-----------------------------

HashMap in java with examples

HashMap is most common Collection which we use now a days. It stores entry in key value pair.
  1. HashMap implements Map interface which maps key to value.
  2. It is not synchronized and is not thread safe.
  3. Duplicate keys are not allowed
  4. One null key and multiple null values are allowed
HashMap<Integer,String> employeeHashmap=new HashMap<Integer,String>();
employeeHashmap.put(1,"Arpit");
employeeHashmap.put(2,"John"); 

Example:

package org.arpit.java2blog;

import java.util.HashMap;

public class HashMapBuiltMain {

 public static void main(String[] args) {
  HashMap<Integer, String> employeeHashmap = new HashMap<Integer, String>();
  employeeHashmap.put(1, "Arpit");
  employeeHashmap.put(2, "John");
  employeeHashmap.put(3, "Martin");
  employeeHashmap.put(4, "Vaibhav");

  // Iterating HashMap Using keySet() and for each loop
  System.out.println("Iterating HashMap Using keySet() and for each loop");
  System.out.println("-----------------------------");
  for (Integer empId : employeeHashmap.keySet()) {
   System.out.println("EmpId:" + empId + " and  Emp Name:" + employeeHashmap.get(empId));

  }
  System.out.println("-----------------------------");
 }
}

When you run above program, you will get below output
Iterating HashMap Using keySet() and for each loop
-----------------------------
EmpId:1 and  Emp Name:Arpit
EmpId:2 and  Emp Name:John
EmpId:3 and  Emp Name:Martin
EmpId:4 and  Emp Name:Vaibhav
-----------------------------

Storing Custom objects as Key:

You can store custom objects as Key in HashMap but you should implement hashcode and equals method, otherwise it may not work as expected.  You may go through hashcode and equal method to understand it better.

Create a class called Country.java
package org.arpit.java2blog;  
public class Country  {  
  
 String name;  
 long population;  
   
 public Country(String name, long population) {  
  super();  
  this.name = name;  
  this.population = population;  
 }  
 public String getName() {  
  return name;  
 }  
 public void setName(String name) {  
  this.name = name;  
 }  
 public long getPopulation() {  
  return population;  
 }  
 public void setPopulation(long population) {  
  this.population = population;  
 }
 
@Override
public int hashCode() {
 final int prime = 31;
 int result = 1;
 result = prime * result + ((name == null) ? 0 : name.hashCode());
 result = prime * result + (int) (population ^ (population >>> 32));
 return result;
}
@Override
public boolean equals(Object obj) {
 if (this == obj)
  return true;
 if (obj == null)
  return false;
 if (getClass() != obj.getClass())
  return false;
 Country other = (Country) obj;
 if (name == null) {
  if (other.name != null)
   return false;
 } else if (!name.equals(other.name))
  return false;
 return true;
}
  
}  

Create another class HashMapMain.java
package org.arpit.java2blog;

import java.util.HashMap;

public class HashMapMain {

 public static void main(String args[])
 {
 // HashMap with Country name as key and capital as value
 // HashMap stores elements in key value pairs
  HashMap<String,String> countryCapitalMap=new HashMap<String,String>();
  countryCapitalMap.put("India","Delhi");
  countryCapitalMap.put("Japan","Tokyo");
  countryCapitalMap.put("France","Paris");
  countryCapitalMap.put("Russia","Moscow");

  System.out.println("-----------------------------");
  // Iterating HashMap Using keySet() and for each loop
  System.out.println("Iterating HashMap Using keySet() and for each loop");
  for (String countryKey:countryCapitalMap.keySet()) {
   System.out.println("Country:"+ countryKey +" and  Capital:"+countryCapitalMap.get(countryKey));

  }
  System.out.println("-----------------------------");
}

}

When you run above program, you will get below output
-----------------------------
Iterating HashMap Using keySet() and for each loop
Country:France and  Capital:Paris
Country:Russia and  Capital:Moscow
Country:Japan and  Capital:Tokyo
Country:India and  Capital:Delhi
-----------------------------


HashMap is not synchronized by default but we can make it synchronized using
Collections.synchronizedMap(new HashMap<String, String>());






TreeMap in java with examples

TreeMap class implements Map similar to HashMap.

Some important points about TreeMap:
  1. TreeMap implements Map interface and extends HashMap class.
  2. TreeMap is implemented using Red black tree based NavigableMap.
  3. TreeMap is ordered collection and store its elements in natural ordering of keys.
  4. Key which you would like to put in TreeMap must implement Comaparable interface or you can use Comparator for custom sorting
Example:
package org.arpit.java2blog;

import java.util.TreeMap;

public class TreeMapMain {

 public static void main(String args[])
 {
 // TreeMap with Country as key and capital as value
 // TreeMap stores elements in natural ordering of keys. 
  TreeMap<String,String> countryCapitalMap=new TreeMap<String,String>();
  countryCapitalMap.put("India","Delhi");
  countryCapitalMap.put("Japan","Tokyo");
  countryCapitalMap.put("France","Paris");
  countryCapitalMap.put("Russia","Moscow");

  System.out.println("-----------------------------");
  // Iterating TreeMap Using keySet() and for each loop
  System.out.println("Iterating TreeMap Using keySet() and for each loop");
  for (String countryKey:countryCapitalMap.keySet()) {
   System.out.println("Country:"+ countryKey +" and  Capital:"+countryCapitalMap.get(countryKey));

  }
  System.out.println("-----------------------------");
}

}

When you run above program, you will get following output:
-----------------------------
Iterating TreeMap Using keySet() and for each loop
Country:France and  Capital:Paris
Country:India and  Capital:Delhi
Country:Japan and  Capital:Tokyo
Country:Russia and  Capital:Moscow
-----------------------------

As you can see, it is sorted in ascending order of Key(Country)

What if you want custom sorting rather than natural ordering:

If you want custom sorting , then you can using below TreeMap constructor. You can define your own comparator.
 TreeMap countryCapitalMap=new TreeMap(Comparator comp);
Example: Create Country.java as below
package org.arpit.java2blog;  
public class Country {  
  
 String name;  
 long population;  
   
 public Country(String name, long population) {  
  super();  
  this.name = name;  
  this.population = population;  
 }  
 public String getName() {  
  return name;  
 }  
 public void setName(String name) {  
  this.name = name;  
 }  
 public long getPopulation() {  
  return population;  
 }  
 public void setPopulation(long population) {  
  this.population = population;  
 }  
       
}  
Create TreeMapCompMain as below:
package org.arpit.java2blog;

import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeMap;

public class TreeMapCompMain {

 public static void main(String[] args)
 {
  Country india=new Country("India",1000);  
        Country japan=new Country("Japan",10000);  
            
        Country france=new Country("France",2000);  
        Country russia=new Country("Russia",20000);  
            
        Comparator<Country> comparator=new Comparator<Country>() {

   @Override
   public int compare(Country o1, Country o2) {
    return o2.getName().compareTo(o1.getName());
   }
  };
  
  System.out.println("Sorting TreeMap in reverse order of country name");
        TreeMap<Country, String> countryCapitalMap=new TreeMap<Country,String>(comparator);  
        countryCapitalMap.put(india,"Delhi");  
        countryCapitalMap.put(japan,"Tokyo");  
        countryCapitalMap.put(france,"Paris");  
        countryCapitalMap.put(russia,"Moscow");  
            
        Iterator<Country> countryCapitalIter=countryCapitalMap.keySet().iterator();//put debug point at this line  
        while(countryCapitalIter.hasNext())  
        {  
            Country countryObj=countryCapitalIter.next();  
            String capital=countryCapitalMap.get(countryObj);  
            System.out.println(countryObj.getName()+"----"+capital);  
            }  
        }  

}

When you run above program, you will get below output:
Sorting TreeMap in reverse order of country name
Russia----Moscow
Japan----Tokyo
India----Delhi
France----Paris

You can pass HashMap to constructor of TreeMap to sort it on Key

 TreeMap countryCapitalMap=new TreeMap(Map hm);

By passing HashMap to constructor of TreeMap, you can sort TreeMap.

Example: 
Create Country.java as below. It should implement Comparable interface

package org.arpit.java2blog;  
public class Country implements Comparable {  
  
 String name;  
 long population;  
   
 public Country(String name, long population) {  
  super();  
  this.name = name;  
  this.population = population;  
 }  
 public String getName() {  
  return name;  
 }  
 public void setName(String name) {  
  this.name = name;  
 }  
 public long getPopulation() {  
  return population;  
 }  
 public void setPopulation(long population) {  
  this.population = population;  
 }
@Override
public int compareTo(Object o) {
    Country country=(Country) o;
 return this.getName().compareTo(country.getName());
}  
       
}  

Create TreeMapCompMain.java as below:
package org.arpit.java2blog;

import java.util.HashMap;
import java.util.Iterator;
import java.util.TreeMap;

public class TreeMapCompMain {

 public static void main(String[] args)
 {
  Country india=new Country("India",1000);  
        Country japan=new Country("Japan",10000);  
            
        Country france=new Country("France",2000);  
        Country russia=new Country("Russia",20000);  
            
        HashMap<Country, String> countryCapitalMap=new HashMap<Country,String>();  
        countryCapitalMap.put(india,"Delhi");  
        countryCapitalMap.put(japan,"Tokyo");  
        countryCapitalMap.put(france,"Paris");  
        countryCapitalMap.put(russia,"Moscow");  
        
        System.out.println("Sorting HashMap by passing it to TreeMap constructor");
        TreeMap<Country,String> sortedTreeMapCountryCapital=new  TreeMap<Country,String> (countryCapitalMap);
        Iterator<Country> countryCapitalIter=sortedTreeMapCountryCapital.keySet().iterator();//put debug point at this line  
        while(countryCapitalIter.hasNext())  
        {  
            Country countryObj=countryCapitalIter.next();  
            String capital=countryCapitalMap.get(countryObj);  
            System.out.println(countryObj.getName()+"----"+capital);  
            }  
        }  

}

When you run program, you will get below output:
Sorting HashMap by passing it to TreeMap constructor
France----Paris
India----Delhi
Japan----Tokyo
Russia----Moscow


LinkedHashMap in java with example

In this post, we will see about LinkedHashMap in java. LinkedHashMap is same as HashMap except that it maintains insertion order.

Some points about LinkedHashMap
  1. LinkedHashMap implements Map interface and extends HashMap class.
  2. LinkedHashMap maintains insertion order, so when you will be able to access elements in the order they were inserted like ArrayList.
  3. LinkedHashMap maintains doubly Linked list to maintain insertion order.

Example:

LinkedHashMapMain.java
package org.arpit.java2blog;

import java.util.LinkedHashMap;

public class LinkedHashMapMain {

 public static void main(String args[])
 {
  // LinkedHashMap with Country as key and capital as value
 // LinkedHashMap maintains insertion order  
  LinkedHashMap<String,String> countryCapitalMap=new LinkedHashMap<String,String>();
  countryCapitalMap.put("India","Delhi");
  countryCapitalMap.put("Japan","Tokyo");
  countryCapitalMap.put("France","Paris");
  countryCapitalMap.put("Russia","Moscow");

  System.out.println("-----------------------------");
  // Iterating Using keySet() and for each loop
  System.out.println("Iterating Using keySet() and for each loop");
  for (String countryKey:countryCapitalMap.keySet()) {
   System.out.println("Country:"+ countryKey +" and  Capital:"+countryCapitalMap.get(countryKey));

  }
  System.out.println("-----------------------------");
}

}

If you may iterate LinkedHashMap in multiple ways.
When you run above program, you will get below output:
-----------------------------
Iterating Using keySet() and for each loop
Country:India and  Capital:Delhi
Country:Japan and  Capital:Tokyo
Country:France and  Capital:Paris
Country:Russia and  Capital:Moscow
-----------------------------

How to calculate difference between two dates in java

In this post, we will see how to calculate difference between two dates. Sometimes we have requirement to find no. of days between two dates or no. of hours between two dates.

Java Program:
package com.org.arpit.java2blog;
 
import java.text.DecimalFormat;
import java.text.SimpleDateFormat;
import java.util.Date;
 
/**
 * @author java2blog.com
 * Arpit Mandliya
 * 
 */ 
public class DateDiff {
 
    public static void main(String[] args) {
        try {
            String date1 = "04/21/2016";
            String date2 = "04/24/2016";
     
            String format = "MM/dd/yyyy";
 
            SimpleDateFormat sdf = new SimpleDateFormat(format);
            Date dateObj1 = sdf.parse(date1);
            Date dateObj2 = sdf.parse(date2);
            
            System.out.println("Date 1:"+dateObj1);
            System.out.println("Date 2:"+dateObj2 + "\n");
 
            // For thousand separator
            DecimalFormat decimalFormatter = new DecimalFormat("###,###");
 
            long diffInMilliSeconds = dateObj2.getTime() - dateObj1.getTime();
 
            System.out.println("difference in milliseconds: " + decimalFormatter.format(diffInMilliSeconds));
            
            int diffsec = (int) (diffInMilliSeconds / (1000));
            System.out.println("difference in seconds: " + decimalFormatter.format(diffsec));
            
            int diffInMin = (int) (diffInMilliSeconds / (60 * 1000));
            System.out.println("difference in minutes: " + decimalFormatter.format(diffInMin));
            
            int diffInHours = (int) (diffInMilliSeconds / (60 * 60 * 1000));
            System.out.println("difference in hours: " + decimalFormatter.format(diffInHours));
            
            int diffInDays = (int) (diffInMilliSeconds / (24 * 60 * 60 * 1000));
            System.out.println("difference in days: " + diffInDays);
 
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
When you run above program, you will get following output:
Date 1:Thu Apr 21 00:00:00 IST 2016
Date 2:Sun Apr 24 00:00:00 IST 2016

difference in milliseconds: 259,200,000
difference between seconds: 259,200
difference in minutes: 4,320
difference in hours: 72
difference in days: 3

How to delete a node from binary search tree in java

In this post, we will see how to delete a node from binary search tree.
There are two parts to it.
  • Search the node
  • After searching that node, delete the node.
There are three cases which we may need to consider while deleting a node from binary search tree.
  • If node has no child
  • If node has one child
  • If node has two children.

If node has no child

It is pretty straight forward case. We need to search the node and make it null.

If node has one children

If node have one children then we need to connect parent of removed node directly to child of the removed node.

If node has two children

It is complicated case. If it has two nodes, we need to connect parent of node to the leftmost node(minimum) of right sub tree or rightmost node(maximum) of left subtree.

Lets understand this case with example:

As you can see, we are replacing node 40 with node 50. Node 50 is minimum element in right subtree of 40 and deleting node 50 after moving as there will duplicate nodes.

Why minimum element of right sub tree?

Here we are using binary search tree property that tree can be represented in multiple ways.

For example:

We are using same property while deleting nodes with two children.

Complete java program:

package org.arpit.java2blog;

public class BinarySearchTreeMain {
 public static class TreeNode {
  int data;
  TreeNode left;
  TreeNode right;

  TreeNode(int data) {
   this.data = data;
  }
 }

 // Get minimum element in binary search tree
 public static TreeNode minimumElement(TreeNode root) {
  if (root.left == null)
   return root;
  else {
   return minimumElement(root.left);
  }
 }

 public static TreeNode deleteNode(TreeNode root, int value) {
  if (root == null)
   return null;
  if (root.data > value) {
   root.left = deleteNode(root.left, value);
  } else if (root.data < value) {
   root.right = deleteNode(root.right, value);

  } else {
   // if nodeToBeDeleted have both children
   if (root.left != null && root.right != null) {
    TreeNode temp = root;
    // Finding minimum element from right
    TreeNode minNodeForRight = minimumElement(temp.right);
    // Replacing current node with minimum node from right subtree
    root.data = minNodeForRight.data;
    // Deleting minimum node from right now
    deleteNode(root.right, minNodeForRight.data);

   }
   // if nodeToBeDeleted has only left child
   else if (root.left != null) {
    root = root.left;
   }
   // if nodeToBeDeleted has only right child
   else if (root.right != null) {
    root = root.right;
   }
   // if nodeToBeDeleted do not have child (Leaf node)
   else
    root = null;
  }
  return root;
 }

 public static TreeNode insert(TreeNode root, TreeNode nodeToBeInserted) {
  if (root == null) {
   root = nodeToBeInserted;
   return root;
  }

  if (root.data > nodeToBeInserted.data) {
   if (root.left == null)
    root.left = nodeToBeInserted;
   else
    insert(root.left, nodeToBeInserted);
  } else if (root.data < nodeToBeInserted.data)
   if (root.right == null)
    root.right = nodeToBeInserted;
   else
    insert(root.right, nodeToBeInserted);
  return root;
 }

 public static void inOrder(TreeNode root) {
  if (root == null)
   return;
  inOrder(root.left);
  System.out.print(root.data + " ");
  inOrder(root.right);
 }

 public static void main(String[] args) {

  // Creating a binary search tree
  TreeNode rootNode = createBinarySearchTree();

  System.out.println("Binary tree:");
  inOrder(rootNode);
  System.out.println();
  System.out.println("Deleting node 40 which have two children:");
  TreeNode rootNodeRes = deleteNode(rootNode, 40);
  inOrder(rootNodeRes);
 }

 public static TreeNode createBinarySearchTree() {
  TreeNode rootNode = new TreeNode(40);
  TreeNode node20 = new TreeNode(20);
  TreeNode node10 = new TreeNode(10);
  TreeNode node30 = new TreeNode(30);
  TreeNode node60 = new TreeNode(60);
  TreeNode node50 = new TreeNode(50);
  TreeNode node70 = new TreeNode(70);
  TreeNode node5 = new TreeNode(5);
  TreeNode node13 = new TreeNode(13);
  TreeNode node55 = new TreeNode(55);

  insert(null, rootNode);
  insert(rootNode, node20);
  insert(rootNode, node10);
  insert(rootNode, node30);
  insert(rootNode, node60);
  insert(rootNode, node50);
  insert(rootNode, node70);
  insert(rootNode, node5);
  insert(rootNode, node13);
  insert(rootNode, node55);
  return rootNode;
 }
}

When you run above program, you will get following output:
Binary tree:
5 10 13 20 30 40 50 55 60 70 
Deleting node 40 which have two children:
5 10 13 20 30 50 55 60 70 


Spring Restful web services CRUD example

This post is in continuation with web service tutorial (Part -15).
    Introduction to web services SOAP web service introduction RESTful web service introduction SOAP web service example in java using eclipse JAX-WS web service eclipse tutorial JAX-WS web service deployment on tomcat Create RESTful web service in java(JAX-RS) using jersey RESTful web service JAXRS json example using jersey RESTful web service JAXRS CRUD example using jersey AngularJS RESTful web service JAXRS CRUD example using $http RESTful Web Services (JAX-RS) @QueryParam Example JAX-RS @MatrixParam Example Spring Restful web services simple example Spring Restful web services json example Spring Restful web services CRUD example
In previous post, we have already seen Spring Restful web services which returns json as response.In this post, we will extend same example and create Restful web services which will provide CRUD(Create, read, update and delete) operation example.

<!-- adsense -->

We will use following annotations for CRUD operation.
Method
Description
Get
It is used to read resource
Post
It is used to create new resource.
It is not idempotent method
Put
It is generally used to update resource.It is idempotent method
Delete
It is used to delete resource

Idempotent means result of multiple successful request will not change state of resource after initial application
For example :
Delete is idempotent method because when you first time use delete, it will delete the resource (initial application) but after that, all other request will have no result because resource is already deleted.

Post is not idempotent method because when you use post to create resource , it will keep creating resource for each new request, so result of multiple successful request will not be same.

Source code:

click to begin
20KB .zip
Here are steps to create a Spring Restful web services  which will provide CRUD opertion.

1) Create a dynamic web project using maven in eclipse named "SpringRestfulWebServicesCRUDExample"

Maven dependencies 

2) We need to add Jackson json utility in the classpath. 
 <dependency>
            <groupId>com.fasterxml.jackson.core</groupId>
            <artifactId>jackson-databind</artifactId>
             <version>2.4.1</version>
 </dependency>

Spring will load Jackson2JsonMessageConverter into its application context automatically. Whenever you request resource as json with accept headers="Accept=application/json", then Jackson2JsonMessageConverter comes into picture and convert resource to json format.
Now change pom.xml as follows:
pom.xml
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
  xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
  <modelVersion>4.0.0</modelVersion>
  <groupId>com.arpit.java2blog</groupId>
  <artifactId>SpringRestfulWebServicesWithJSONExample</artifactId>
  <packaging>war</packaging>
  <version>0.0.1-SNAPSHOT</version>
  <name>SpringRestfulWebServicesWithJSONExample Maven Webapp</name>
  <url>http://maven.apache.org</url>
  <dependencies>
    <dependency>
      <groupId>junit</groupId>
      <artifactId>junit</artifactId>
      <version>3.8.1</version>
      <scope>test</scope>
    </dependency>
    <dependency>
   <groupId>javax.servlet</groupId>
   <artifactId>javax.servlet-api</artifactId>
   <version>3.1.0</version>
  </dependency>

  <dependency>
   <groupId>org.springframework</groupId>
   <artifactId>spring-core</artifactId>
   <version>${spring.version}</version>
  </dependency>
  <dependency>
   <groupId>org.springframework</groupId>
   <artifactId>spring-webmvc</artifactId>
   <version>${spring.version}</version>
  </dependency>
   <dependency>
            <groupId>com.fasterxml.jackson.core</groupId>
            <artifactId>jackson-databind</artifactId>
             <version>2.4.1</version>
        </dependency>
 </dependencies>
 <build>
  <finalName>SpringRestfulWebServicesWithJSONExample</finalName>

  <plugins>
   <plugin>
    <groupId>org.apache.maven.plugins</groupId>
    <artifactId>maven-compiler-plugin</artifactId>
    <version>3.1</version>
    <configuration>
     <source>${jdk.version}</source>
     <target>${jdk.version}</target>
    </configuration>
   </plugin>
  </plugins>

 </build>
 <properties>
  <spring.version>4.2.1.RELEASE</spring.version>
  <jdk.version>1.7</jdk.version>
 </properties>
</project>

Spring application configuration:

3) Change web.xml as below:
<!DOCTYPE web-app PUBLIC
 "-//Sun Microsystems, Inc.//DTD Web Application 2.3//EN"
 "http://java.sun.com/dtd/web-app_2_3.dtd" >

<web-app>
  <display-name>Archetype Created Web Application</display-name>
  <servlet>
 <servlet-name>springrest</servlet-name>
 <servlet-class>
  org.springframework.web.servlet.DispatcherServlet
 </servlet-class>
 <load-on-startup>1</load-on-startup>
</servlet>

<servlet-mapping>
 <servlet-name>springrest</servlet-name>
 <url-pattern>/</url-pattern>
</servlet-mapping>
</web-app>


4) create a xml file named springrest-servlet.xml in /WEB-INF/ folder.
Please change context:component-scan if you want to use different package for spring to search for controller.Please refer to spring mvc hello world example for more understanding.

<beans xmlns="http://www.springframework.org/schema/beans"
 xmlns:context="http://www.springframework.org/schema/context"
 xmlns:mvc="http://www.springframework.org/schema/mvc" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
 xsi:schemaLocation=" http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans-3.0.xsd http://www.springframework.org/schema/context 
        http://www.springframework.org/schema/context/spring-context-3.0.xsd http://www.springframework.org/schema/mvc http://www.springframework.org/schema/mvc/spring-mvc-3.0.xsd">

 <mvc:annotation-driven/>
<context:component-scan base-package="org.arpit.java2blog.controller" />

</beans>

Create bean class 

4) Create a bean name "Country.java" in org.arpit.java2blog.bean.
package org.arpit.java2blog.bean;

public class Country{
 
 int id;
 String countryName; 
 long population;
 
 public Country() {
  super();
 }
 public Country(int i, String countryName,long population) {
  super();
  this.id = i;
  this.countryName = countryName;
  this.population=population;
 }
 public int getId() {
  return id;
 }
 public void setId(int id) {
  this.id = id;
 }
 public String getCountryName() {
  return countryName;
 }
 public void setCountryName(String countryName) {
  this.countryName = countryName;
 }
 public long getPopulation() {
  return population;
 }
 public void setPopulation(long population) {
  this.population = population;
 } 
 
}

Create Controller 

5) Create a controller named "CountryController.java" in package org.arpit.java2blog.controller
package org.arpit.java2blog.controller;

import java.util.List;
import org.arpit.java2blog.bean.Country;
import org.arpit.java2blog.service.CountryService;
import org.springframework.web.bind.annotation.PathVariable;
import org.springframework.web.bind.annotation.RequestBody;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;
import org.springframework.web.bind.annotation.RestController;

@RestController
public class CountryController {

	CountryService countryService = new CountryService();

	@RequestMapping(value = "/countries", method = RequestMethod.GET, headers = "Accept=application/json")
	public List<Country> getCountries() {
		List<Country> listOfCountries = countryService.getAllCountries();
		return listOfCountries;
	}

	@RequestMapping(value = "/country/{id}", method = RequestMethod.GET, headers = "Accept=application/json")
	public Country getCountryById(@PathVariable int id) {
		return countryService.getCountry(id);
	}

	@RequestMapping(value = "/countries", method = RequestMethod.POST, headers = "Accept=application/json")
	public Country addCountry(@RequestBody Country country) {
		return countryService.addCountry(country);
	}

	@RequestMapping(value = "/countries", method = RequestMethod.PUT, headers = "Accept=application/json")
	public Country updateCountry(@RequestBody Country country) {
		return countryService.updateCountry(country);

	}

	@RequestMapping(value = "/country/{id}", method = RequestMethod.DELETE, headers = "Accept=application/json")
	public void deleteCountry(@PathVariable("id") int id) {
		countryService.deleteCountry(id);

	}	
}
@Path(/your_path_at_class_level) : Sets the path to base URL + /your_path_at_class_level. The base URL is based on your application name, the servlet and the URL pattern from the web.xml" configuration file.

@Path(/your_path_at_method_level): Sets path to base URL + /your_path_at_class_level+ /your_path_at_method_level

@Produces(MediaType.APPLICATION_JSON[, more-types ]): @Produces defines which MIME type is delivered by a method annotated with @GET. In the example text ("text/json") is produced.

Create Service class

6) Create a class CountryService.java in package org.arpit.java2blog.service
It is just a helper class which should be replaced by database implementation. It is not very well written class, it is just used for demonstration.
package org.arpit.java2blog.service;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

import org.arpit.java2blog.bean.Country;

/*
 * It is just a helper class which should be replaced by database implementation.
 * It is not very well written class, it is just used for demonstration.
 */
public class CountryService {

 static HashMap<Integer,Country> countryIdMap=getCountryIdMap();


 public CountryService() {
  super();

  if(countryIdMap==null)
  {
   countryIdMap=new HashMap<Integer,Country>();
  // Creating some objects of Country while initializing
   Country indiaCountry=new Country(1, "India",10000);
   Country chinaCountry=new Country(4, "China",20000);
   Country nepalCountry=new Country(3, "Nepal",8000);
   Country bhutanCountry=new Country(2, "Bhutan",7000);


   countryIdMap.put(1,indiaCountry);
   countryIdMap.put(4,chinaCountry);
   countryIdMap.put(3,nepalCountry);
   countryIdMap.put(2,bhutanCountry);
  }
 }

 public List<Country> getAllCountries()
 {
  List<Country> countries = new ArrayList<Country>(countryIdMap.values());
  return countries;
 }

 public Country getCountry(int id)
 {
  Country country= countryIdMap.get(id);
  return country;
 }
 public Country addCountry(Country country)
 {
  country.setId(getMaxId()+1);
  countryIdMap.put(country.getId(), country);
  return country;
 }
 
 public Country updateCountry(Country country)
 {
  if(country.getId()<=0)
   return null;
  countryIdMap.put(country.getId(), country);
  return country;

 }
 public void deleteCountry(int id)
 {
  countryIdMap.remove(id);
 }

 public static HashMap<Integer, Country> getCountryIdMap() {
  return countryIdMap;
 }
 
 // Utility method to get max id
 public static int getMaxId()
 {   int max=0;
 for (int id:countryIdMap.keySet()) {  
  if(max<=id)
   max=id;

 }  
 return max;
 }
}



7) It 's time to do maven build.
Right click on project -> Run as -> Maven build

8) Provide goals as clean install (given below) and click on run

Run the application

9) Right click on project -> run as -> run on server
Select apache tomcat and click on finish

10) We will test this application in  postman , UI based client for testing restful web applications. It is chrome plugin. Launch postman.

Get method

11) Test your get method Spring REST service
URL :"http://localhost:8080/SpringRestfulWebServicesCRUDExample/countries".
You will get following output:

Post method

12) Post method is used to create new resource. Here we are adding new Country England to country list, so you can see we have used new country json in post body.
URL: "http://localhost:8080/SpringRestfulWebServicesCRUDExample/countries".

Use get method to check if above country have been added to country list.


Put Method

13) Put method is used to update resource. Here will update population of nepal using put method.
We will update country json in body of request.
URL : "http://localhost:8080/SpringRestfulWebServicesCRUDExample/countries"


Use get method to check population of nepal.


Delete method

14) Delete method is used to delete resource.We will pass id of country which needs to be deleted as PathParam. We are going delete id:4 i.e. china to demonstrate delete method.

URL : "http://localhost:8080/SpringRestfulWebServicesCRUDExample/country/4"


Use get method to check country list.


As you can see, we have deleted country with id 4 i.e. china

Project structure:


We are done with Spring Restful web services json CRUD example. If you are still facing any issue, please comment.

If you getting 404 error with above steps, you may need to follow below steps:


1) If you are getting this warning into your Tomcat startup console log, then it can cause the issue

WARNING: [SetPropertiesRule]{Server/Service/Engine/Host/Context} Setting property 'source' to 'org.eclipse.jst.j2ee.server: JAXRSJsonCRUDExample' did not find a matching property.

This particular warning basically means that the <Context> element in Tomcat's server.xml contains an unknown attribute source and that Tomcat doesn't know what to do with this attribute and therefore will ignore it.
To resolve this in eclipse,
Remove the project from the server from the Server View. Right click on server -> add and remove

then remove project from server configuration.
Then run the project under the same server. Warning should be removed now
Or if warning still remains then
  • Go to server view
  • Double click on your tomcat server. It will open the server configuration.
  • Under server options check ‘Publish module contents to separate XML files’ checkbox. 
  • Restart your server. This time your page will come without any issues.
2) Try to update Maven project.
Right click on project ->Maven-> update project
then

This should solve you issues.

Binary search tree in java

Binary search tree is a special type of binary tree which have following properties.
  • Nodes which are smaller than root will be in left subtree.
  • Nodes which are greater than root will be right subtree.
  • It should not have duplicate nodes
  • Both left and right subtree also should be binary search tree.
Example of binary search tree:
Lets perform following operation on binary search tree
  • Find
  • Insert

Search()

Searching a node in binary search is very easy. You just need to traverse left (if smaller) and right (if greater) according to value to be found.

Algorithm:

  • If node to be found is equal to root, then search is successful
  • If node to be found is smaller than root , then traverse left subtree.
  • If node to be found is greater than root, then traverse right subtree
  • Repeat above steps recursively until you find the node.



Insert()

Insert node operation is also easy operation. You just need to compare it with root and traverse left (if smaller) or right(if greater) according to value of node to be inserted.

Algorithm:

  • Make root node as current node
  • If node to be inserted < root
    • If it has left child then traverse left
    • If it do not have left child, insert node here
  • If node to be inserted > root
    • If it have right child, traverse right
    • If it do not have right child, insert node here.

Complete java program:

package org.arpit.java2blog;

public class BinarySearchTreeMain {
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
 
 public static boolean search(TreeNode root,TreeNode nodeToBeSearched)
 {
  if(root==null)
   return false;
  if(root.data== nodeToBeSearched.data)
  {
   return true;
  }
  boolean result=false;
  if(root.data > nodeToBeSearched.data)
   result=search(root.left,nodeToBeSearched);
  else if(root.data < nodeToBeSearched.data)
   result= search(root.right,nodeToBeSearched);
  return result;
 }
 
 
 public static TreeNode insert(TreeNode root,TreeNode nodeToBeInserted)
 {
  if(root==null)
  {
   root=nodeToBeInserted;
   return root;
  }
  
  if(root.data > nodeToBeInserted.data)
  {
   if(root.left==null)
    root.left=nodeToBeInserted;
   else
    insert(root.left,nodeToBeInserted);
  }
  else if(root.data < nodeToBeInserted.data)
   if(root.right==null)
    root.right=nodeToBeInserted;
   else
    insert(root.right,nodeToBeInserted);
  return root;
 } 
 
 public static void inOrder(TreeNode root)
 {
  if(root==null)
   return;
  inOrder(root.left);
  System.out.print(root.data+" ");
  inOrder(root.right);
 }
 public static void main(String[] args)
 {
  
  // Creating a binary search tree
  TreeNode rootNode=createBinarySearchTree();
  TreeNode node55=new TreeNode(55);
  boolean result=search(rootNode,node55);
  System.out.println("Searching for node 55 : "+result);
  System.out.println("---------------------------");
  TreeNode node13=new TreeNode(13);
  TreeNode root=insert(rootNode,node13);
  System.out.println("Inorder traversal of binary tree after adding 13:");
  inOrder(root);
 
 }   
 
 public static TreeNode createBinarySearchTree()
 {
  TreeNode rootNode =new TreeNode(40);
  TreeNode node20=new TreeNode(20);
  TreeNode node10=new TreeNode(10);
  TreeNode node30=new TreeNode(30);
  TreeNode node60=new TreeNode(60);
  TreeNode node50=new TreeNode(50);
  TreeNode node70=new TreeNode(70);
  TreeNode node5=new TreeNode(5);
         TreeNode node55=new TreeNode(55);

  insert(null,rootNode);
  insert(rootNode,node20);
  insert(rootNode,node10);
  insert(rootNode,node30);
  insert(rootNode,node60);
  insert(rootNode,node50);
  insert(rootNode,node70);
  insert(rootNode,node5);
  insert(rootNode,node55);
  return rootNode;
 }

}

When you run above program, you will get below output:
Searching for node 55 : true
---------------------------
Inorder traversal of binary tree after adding 13:
5 10 13 20 30 40 50 55 60 70 

Find minimum and maximum elements in binary search tree in java

In this post, we will see how to find minimum and maximum elements in binary search tree.

Finding minimum element:

Minimum element is nothing but leftmost node in binary search tree, so traverse left until you get leftmost element.
// Get minimum element in binary search tree
 public static TreeNode minimumElement(TreeNode root)
 {
  if(root.left==null)
   return root;
  else
  {
   return minimumElement(root.left);
  }
 }

Finding maximum element:

Maximum element is nothing but rightmost node in binary search tree, so traverse right until you get rightmost element.
// Get maximum element in binary search tree
 public static TreeNode maximumElement(TreeNode root)
 {
  if(root.right==null)
   return root;
  else
  {
   return maximumElement(root.right);
  }
 }

Complete java program:

package org.arpit.java2blog;

public class BinarySearchTreeMain {
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
 public static boolean search(TreeNode root,TreeNode nodeToBeSearched)
 {
  if(root==null)
   return false;
  if(root.data== nodeToBeSearched.data)
  {
   return true;
  }
  boolean result=false;
  if(root.data > nodeToBeSearched.data)
   result=search(root.left,nodeToBeSearched);
  else if(root.data < nodeToBeSearched.data)
   result= search(root.right,nodeToBeSearched);
  return result;
 }
 
 // Get minimum element in binary search tree
 public static TreeNode minimumElement(TreeNode root)
 {
  if(root.left==null)
   return root;
  else
  {
   return minimumElement(root.left);
  }
 }
 
 // Get maximum element in binary search tree
 public static TreeNode maximumElement(TreeNode root)
 {
  if(root.right==null)
   return root;
  else
  {
   return maximumElement(root.right);
  }
 }
 public static TreeNode insert(TreeNode root,TreeNode nodeToBeInserted)
 {
  if(root==null)
  {
   root=nodeToBeInserted;
   return root;
  }
  
  if(root.data > nodeToBeInserted.data)
  {
   if(root.left==null)
    root.left=nodeToBeInserted;
   else
    insert(root.left,nodeToBeInserted);
  }
  else if(root.data < nodeToBeInserted.data)
   if(root.right==null)
    root.right=nodeToBeInserted;
   else
    insert(root.right,nodeToBeInserted);
  return root;
 } 
 
 public static void inOrder(TreeNode root)
 {
  if(root==null)
   return;
  inOrder(root.left);
  System.out.print(root.data+" ");
  inOrder(root.right);
 }
 public static void main(String[] args)
 {
  
  // Creating a binary search tree
  TreeNode rootNode=createBinarySearchTree();
  System.out.println("Minimum element in binary search tree: "+minimumElement(rootNode).data);
  System.out.println("Maximum element in binary search tree: "+maximumElement(rootNode).data);
  
 }   
 
 
 public static TreeNode createBinarySearchTree()
 {
  TreeNode rootNode =new TreeNode(40);
  TreeNode node20=new TreeNode(20);
  TreeNode node10=new TreeNode(10);
  TreeNode node30=new TreeNode(30);
  TreeNode node60=new TreeNode(60);
  TreeNode node50=new TreeNode(50);
  TreeNode node70=new TreeNode(70);
  TreeNode node5=new TreeNode(5);
     TreeNode node55=new TreeNode(55);

  insert(null,rootNode);
  insert(rootNode,node20);
  insert(rootNode,node10);
  insert(rootNode,node30);
  insert(rootNode,node60);
  insert(rootNode,node50);
  insert(rootNode,node70);
  insert(rootNode,node5);
  insert(rootNode,node55);
  
  return rootNode;
 }

}

When you run above program, you will get below output:
Minimum element in binary search tree: 5
Maximum element in binary search tree: 70

jQuery Selector examples

jQuery selectors are important part of jQuery. It is used to select DOM elements and manipulate it.

Syntax:
It should start with $ followed by parenthesis.
For below html, you want to hide text on click of button.

So you need to select button with id "myButton" as $("#myButton") and div with id helloWorldDiv as $("#helloWorldDiv")

For example:
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>jQuery</title>
<script src="http://code.jquery.com/jquery-2.2.3.min.js"></script>
<script>
  $(document).ready(function() {
  $("#myButton").click(function() { $("#helloWorldDiv").hide()
  });

});  
</script>
</head>
<body>    
<button id="myButton">Hide text</button>
</br>
</br>
<div id="helloWorldDiv">Hello world</div> 
</body>
</html>

Live demo :
jQuery selector example

So here on button click , we have hidden helloWorldDiv text.

Example on various selectors :

Element selector:

If you just write element name with $(), it will select all those element of that type.
For example: if you use $("div") , it will select all the div element in DOM.
In this example, on click of button , we will change text of all div present in the DOM.
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>jQuery</title>
<script src="http://code.jquery.com/jquery-2.2.3.min.js"></script>
<script>
  $(document).ready(function() {
  $("#myButton").click(function() { $("div").html("Hello java2blog")
  });

});  
</script>
</head>
<body>    
<button id="myButton">Change all div text</button>
</br>
</br>
<div id="helloWorldDiv">Hello John</div>

<div id="helloWorldDiv">Hello Martin</div>

<div id="helloWorldDiv">Hello Smith</div>
</body>
</html>

Live demo:
jQuery element selector example

#Id selector :

For selecting element with id, you need to use $(#id).

Example:
So you need to select button with id "myButton" as $("#myButton") and div with id helloWorldDiv as $("#helloWorldDiv")
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>jQuery</title>
<script src="http://code.jquery.com/jquery-2.2.3.min.js"></script>
<script>
  $(document).ready(function() {
  $("#myButton").click(function() { $("#helloWorldDiv").hide()
  });

});  
</script>
</head>
<body>    
<button id="myButton">Hide text</button>
</br>
</br>
<div id="helloWorldDiv">Hello world</div> 
</body>
</html>

Live demo :
jQuery id selector example

So here on button click , we have hidden helloWorldDiv text.

class selector:

You can get all elements which use some class of CSS.
You need to use $(.className) to select all elements which uses that class. Example:
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>jQuery</title>
<script src="http://code.jquery.com/jquery-2.2.3.min.js"></script>
<script>
  $(document).ready(function() {
   $(".abc").css("background-color","orange");

});  
</script>
</head>
<body>    
<div id="helloWorldDiv" class ="abc">Hello John</div>

<div id="helloWorldDiv">Hello Martin</div>

<div id="helloWorldDiv" class ="abc">Hello Smith</div>
</body>
</html>

Live Demo:
jQuery class selector example

For more jQuery selectors, please refer jQuery selector API

Lowest Common Ancestor (LCA) of binary search tree in java

In this post, we will see how to find lowest common ancestor(LCA) of two nodes in binary search tree.
We have already seen how to find LCA in binary tree. It is much simple than that.
Lets understand with example.

As you can see here, LCA is nothing but lowest common parent of two nodes.

Recursive Algorithm (For nodes A and B):

  • If node is null, return it
  • If node is greater than A and B, traverse left subtree
  • If node is lesser than A and B , traverse right subtree.
  • If above both condition do not satisfy, then node is LCA of A and B
public static TreeNode lowestCommonAncestorForBinarySearchTree(TreeNode root, TreeNode a, TreeNode b) {
   if(root==null)
    return null;;
        if(root.data>a.data && root.data > b.data)
        {
         return lowestCommonAncestorForBinarySearchTree(root.left,a,b);
        }
        else if(root.data < a.data && root.data < b.data)
        {
       return  lowestCommonAncestorForBinarySearchTree(root.right,a,b);
        }
        // if you reach at this place, then it is LCA for given two nodes because a and b are on either side of root. 
        return root;
        
     }

Iterative solution:

It is similar to recursive solution, here we are using while loop to traverse nodes.
public static TreeNode LCAItr(TreeNode root, TreeNode a, TreeNode b) {
   while(root!=null)
   {
        if(root.data>a.data && root.data > b.data)
        {
         root=root.left;
        }
        else if(root.data < a.data && root.data < b.data)
        {
       root=root.right;
        }
        else
        {
         return root;
        }
   } 
        return root;
   }

Complete java program:

package org.arpit.java2blog;


public class BinaryTree {
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }

 
   public static TreeNode lowestCommonAncestorForBinarySearchTree(TreeNode root, TreeNode a, TreeNode b) {
   if(root==null)
    return null;;
        if(root.data>a.data && root.data > b.data)
        {
         return lowestCommonAncestorForBinarySearchTree(root.left,a,b);
        }
        else if(root.data < a.data && root.data < b.data)
        {
       return  lowestCommonAncestorForBinarySearchTree(root.right,a,b);
        }
        // if you reach at this place, then it is LCA for given two nodes because a and b are on either side of root. 
        return root;
        
     }
  
  public static TreeNode LCAItr(TreeNode root, TreeNode a, TreeNode b) {
   while(root!=null)
   {
        if(root.data>a.data && root.data > b.data)
        {
         root=root.left;
        }
        else if(root.data < a.data && root.data < b.data)
        {
       root=root.right;
        }
        else
        {
         return root;
        }
   } 
        return root;
   }
     
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Lowest common ancestor for node 5 and 30 using Recursion:");
  TreeNode node5=new TreeNode(5);
  TreeNode node30=new TreeNode(30);
  System.out.println(lowestCommonAncestorForBinarySearchTree(rootNode,node5,node30).data);
  
  System.out.println("Lowest common ancestor for node 5 and 30 using Iteration:");
  System.out.println(LCAItr(rootNode,node5,node30).data);
 
 }
 
 

 public static TreeNode createBinaryTree()
 {

  TreeNode rootNode =new TreeNode(40);
  TreeNode node20=new TreeNode(20);
  TreeNode node10=new TreeNode(10);
  TreeNode node30=new TreeNode(30);
  TreeNode node60=new TreeNode(60);
  TreeNode node50=new TreeNode(50);
  TreeNode node70=new TreeNode(70);
  TreeNode node5=new TreeNode(5);
  TreeNode node45=new TreeNode(45);
  TreeNode node55=new TreeNode(55);

  rootNode.left=node20;
  rootNode.right=node60;

  node20.left=node10;
  node20.right=node30;

  node60.left=node50;
  node60.right=node70;

  node10.left=node5;
  node50.right=node55;
  return rootNode;
 }
}


When you run above program, you will get below output:
Lowest common ancestor for node 5 and 30 using Recursion:
20
Lowest common ancestor for node 5 and 30 using Iteration:
20

Please go through java interview programs for more such programs.

Lowest Common Ancestor (LCA) of binary tree in java

In this post, we will see how to find lowest common ancestor(LCA) of two nodes in binary tree. Lets understand with example.

As you can see here, LCA is nothing but lowest common parent of two nodes.

Recursive Algorithm (For nodes A and B):

  • If node is null, return it
  • If we find A or B, return it.
  • Traverse left subtree and right subtree
  •  If we get both left and right for any node as not null, it will be lowest common ancestor of two given nodes 
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode a, TreeNode b) {
         if(root == null)
         return null;
         if(root.data == a.data || root.data == b.data )
         return root;
         
         TreeNode left=lowestCommonAncestor(root.left,a,b);
         TreeNode right=lowestCommonAncestor(root.right,a,b);
         
         // If we get left and right not null , it is lca for a and b
         if(left!=null && right!=null)
             return root;
         if(left== null)
         return right;
         else
         return left;
             
     }

Complete java program:

package org.arpit.java2blog;


public class BinaryTree {
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }

  public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode a, TreeNode b) {
         if(root == null)
         return null;
         if(root.data == a.data || root.data == b.data )
         return root;
         
         TreeNode left=lowestCommonAncestor(root.left,a,b);
         TreeNode right=lowestCommonAncestor(root.right,a,b);
         
         // If we get left and right not null , it is lca for a and b
         if(left!=null && right!=null)
             return root;
         if(left== null)
         return right;
         else
         return left;
             
     }
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Lowest common ancestor for node 5 and 30:");
  TreeNode node5=new TreeNode(5);
  TreeNode node30=new TreeNode(30);
  System.out.println(lowestCommonAncestor(rootNode,node5,node30).data);
 
 }
 
 

 public static TreeNode createBinaryTree()
 {

  TreeNode rootNode =new TreeNode(40);
  TreeNode node20=new TreeNode(20);
  TreeNode node10=new TreeNode(10);
  TreeNode node30=new TreeNode(30);
  TreeNode node60=new TreeNode(60);
  TreeNode node50=new TreeNode(50);
  TreeNode node70=new TreeNode(70);
  TreeNode node5=new TreeNode(5);
  TreeNode node45=new TreeNode(45);
  TreeNode node55=new TreeNode(55);

  rootNode.left=node20;
  rootNode.right=node60;

  node20.left=node10;
  node20.right=node30;

  node60.left=node50;
  node60.right=node70;

  node10.left=node5;
  node50.right=node55;
  return rootNode;
 }
}


When you run above program, you will get below output:
Lowest common ancestor for node 5 and 30:
20

Java Binary tree tutorial:

    Binary tree in java Binary tree preorder traversal Binary tree postorder traversal Binary tree inorder traversal Binary tree level order traversal Binary tree spiral order traversal Binary tree reverse level order traversal Binary tree boundary traversal Print leaf nodes of binary tree Count leaf nodes in binary tree get maximum element in binary tree Print all paths from root to leaf in binary tree Print vertical sum of binary tree in java Get level of node in binary tree in java Lowest common ancestor(LCA) in binary tree in java

Please go through java interview programs for more such programs.