If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
This is 8th part of java binary tree tutorial.

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 Print leaf nodes of binary tree Count leaf nodes 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

In this post, we will see about program to count leaf nodes in a binary tree in java

Algorithm-

Steps for counting number of leaf nodes are:
  • If node is null then return 0
  • If encountered leaf node(i.e. node.left is null and node.right is null) then return 1.
  • Recursively calculate number of leaf nodes using
  • Number of leaf nodes= number of leaf nodes in left subtree + number of leaf nodes in right sub tree
    
Code for recursion will be:
/* To get the count of leaf nodes in a binary tree*/
 public static  int getLeafCountOfBinaryTree(TreeNode node)
 {
   if(node == null)      
     return 0;
   if(node.left ==null && node.right==null)     
     return 1;           
   else
     return getLeafCountOfBinaryTree(node.left)+ getLeafCountOfBinaryTree(node.right);     
}


Lets create java program for counting number of leaf nodes:
 
package org.arpit.java2blog;

public class BinaryTree {

 
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
 // Recursive Solution
/* To get the count of leaf nodes in a binary tree*/
public static  int getLeafCountOfBinaryTree(TreeNode node)
{
  if(node == null)      
    return 0;
  if(node.left ==null && node.right==null)     
    return 1;           
  else
    return getLeafCountOfBinaryTree(node.left)+ getLeafCountOfBinaryTree(node.right);     
}

 
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Number of leaf nodes in binary tree :"+getLeafCountOfBinaryTree(rootNode));
 }
 
 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);
  
  rootNode.left=node20;
  rootNode.right=node60;
  
  node20.left=node10;
  node20.right=node30;
  
  node60.left=node50;
  node60.right=node70;
  
  return rootNode;
 }
}

Run above program and you will get following output:
 
Number of leaf nodes in binary tree :4

Please go through Frequently asked java interview programs  for more such programs.

This is 7th part of java binary tree tutorial.

In this post, we will see about program to print leaf nodes in a binary tree in java

Algorithm-

Steps for counting number of leaf nodes are:
  • If node is null then return 0
  • If encounterd leaf node(i.e. node.left is null and node.right is null) then print the node.
  • Recursively visit leaf subtree and right subtree.
Code for recursion will be:
 // print leaf nodes
 public static void printLeafNodes(TreeNode node) {
 
   if(node==null)
    return;
   
   if(node.left == null && node.right == null) {
    System.out.printf("%d ",node.data);
   }
   printLeafNodes(node.left);
   printLeafNodes(node.right);
 }



Example:
Binary tree:

Lets create java program for counting number of leaf nodes:
 
package org.arpit.java2blog;

public class BinaryTree {

 
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
 // Recursive Solution
 // print leaf nodes
 public static void printLeafNodes(TreeNode node) {
 
   if(node==null)
    return;
   
   if(node.left == null && node.right == null) {
    System.out.printf("%d ",node.data);
   }
   printLeafNodes(node.left);
   printLeafNodes(node.right);
 }


 
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  System.out.println("Printing leaf nodes in binary tree :");
  printLeafNodes(rootNode);
 }
 
 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 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;
 }
}

Run above program and you will get following output:
 
Printing leaf nodes in binary tree :
5 30 55 70 

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

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
This is 5th part of java binary tree tutorial.

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 Print leaf nodes of binary tree Count leaf nodes 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
In this post, we will see about Level Order binary tree traversal in java.

Level Order traversal:

Level order traversal of below tree will be:



We will use Queue for Level Order traversal.This algorithm is very similar to Breadth first search of graph.
Steps for Level order traversal algorithm:
  1. Create empty queue and pust root node to it.
  2. Do the following when queue is not empty
    • Pop a node from queue and print it
    • Push left child of popped node to queue if not null
    • Push right child of popped node to queue if not null

 
// prints in level order
 public static void levelOrderTraversal(TreeNode startNode) {
  Queue<TreeNode> queue=new LinkedList<TreeNode>();
  queue.add(startNode);
  while(!queue.isEmpty())
  {
   TreeNode tempNode=queue.poll();
   System.out.printf("%d ",tempNode.data);
   if(tempNode.left!=null)
    queue.add(tempNode.left);
   if(tempNode.right!=null)
    queue.add(tempNode.right);
  }
 }

Example:
Lets say your binary tree is :

So Level Order traversal will work as below:

Lets create java program for level order traversal:
 
package org.arpit.java2blog;

import java.util.Queue;
import java.util.LinkedList;
public class BinaryTree {

 
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
// prints in level order
 public static void levelOrderTraversal(TreeNode startNode) {
  Queue<TreeNode> queue=new LinkedList<TreeNode>();
  queue.add(startNode);
         while(!queue.isEmpty())
  {
   TreeNode tempNode=queue.poll();
   System.out.printf("%d ",tempNode.data);
   if(tempNode.left!=null)
    queue.add(tempNode.left);
   if(tempNode.right!=null)
    queue.add(tempNode.right);
  }
 }
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Level Order traversal of binary tree will be:");
  levelOrderTraversal(rootNode);
 }
 
 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);
  
  rootNode.left=node20;
  rootNode.right=node60;
  
  node20.left=node10;
  node20.right=node30;
  
  node60.left=node50;
  node60.right=node70;
  
  return rootNode;
 }
}

Run above program and you will get following output:
 
Level Order traversal of binary tree will be:
40 20 60 10 30 50 70 

Please go through java interview programs for more such programs.

In this post, we will see about Hashset in java

Java HashSet:

Part-1:HashSet in java
Part-2:Difference between HashMap and HashSet 
Part-3:hashcode and equals method in java


This is one of the frequently asked question in core java interview so in this post, we will see how HashSet works in java.We have already seen How hashMap works in java and also difference between HashMap and HashSet.


Lets first see introduction of Hashset then we will go through internals of it.

HashSet:

HashSet implements Set interface which does not allow duplicate value.It is not synchronized and is not thread safe.
Definition of duplicate can be quite tricky sometimes.Lets consider two cases here.
  1. In case of primitive types(such as interger, String)
  2. In case of custom defined objects.
In case of primitive types:
In case of primitives type, it is very straight forward.Lets see with help of example:
Lets create a java program:
package org.arpit.java2blog;
import java.util.HashSet;

public class HashSetMain {

 public static void main(String[] args) {
  HashSet<String> nameSet=new HashSet<String>();
  nameSet.add("Arpit");
  nameSet.add("Arpit");
  nameSet.add("john");
  System.out.println("size of nameSet="+nameSet.size());
  System.out.println(nameSet);
 }

}
When you run above program, you will get following output:
size of nameSet=2
[Arpit, john]
So we tried to add String "Arpit" twice, but as HashSet does not allow duplicate value, it will add "Arpit" once in HashSet

In case of Custom Objects:
For understanding how HashSet will work in case of custom objects, you need to understand hashcode and equals method in java.Lets create a class called Country and implement only equals method in it.
package org.arpit.java2blog;

public class Country {

 String name;
 long 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;
 }
 
 public String toString()
 {
  return name;
 }
 @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 main class:
package org.arpit.java2blog;

import java.util.HashSet;

public class HashSetCountryMain {

 public static void main(String[] args)
 {
  HashSet<Country> countrySet=new HashSet<Country>();
  Country india1=new Country();
  india1.setName("India");
 
  Country india2=new Country();
  india2.setName("India");
  
  countrySet.add(india1);
  countrySet.add(india2);
   
  System.out.println("size of nameSet="+countrySet.size());
  System.out.println(countrySet);
  
 }
}

When you run above program, you will get following output:
size of nameSet=2
[India, India]

Now you must be wondering even through two objects are equal why HashSet contains two values instead of one.This is because First HashSet calculates hashcode for that key object, if hashcodes are same then only it checks for equals method and because hashcode for above two country objects uses default hashcode method,Both will have different memory address hence different hashcode.
Now lets add hashcode method in above Country class
@Override
 public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + ((name == null) ? 0 : name.hashCode());
  return result;
 }
Run above main program again, you will get following output:
size of nameSet=1
[India]

So now we have good understanding of HashSet, lets see its internal representation:

Internal working of HashSet:

When you add any duplicate element to HashSet, add() method returns false and do not add duplicate element to HashSet.
How add method return false? For this, we need to see HashSet's add method in JavaAPI
public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    
    private transient HashMap<E,Object> map;
 
    // PRESENT is dummy value which will be used as value in map
    private static final Object PRESENT = new Object();
    
    /**
     * Constructs a empty map.so hash
     * 
     */
    public HashSet() {
     map = new HashMap<E,Object>();
    }
    
    // return false if e is already present in HashSet
    public boolean add(E e) {
     return map.put(e, PRESENT)==null;
    }
    
    // other HashSet methods
}
So from above code, It is clear that HashSet uses HashMap for checking duplicate elements.As we know that in HashMap , key should be unique. So HashSet uses this concept, When element is added to HashSet, it is added to internal HashMap as Key.This HashMap required some value so a dummy Object(PRESENT) is used as value in this HashMap.
PRESENT is dummy value which is used value for internal map.
Lets see add method:
 // return false if e is already present in HashSet
    public boolean add(E e) {
     return map.put(e, PRESENT)==null;
    }
So here there will be two cases
  • map.put(e,PRESENT) will return null, if element not present in that map. So map.put(e, PRESENT) == null will return true ,hence add method will return true and element will be added in HashSet.
  • map.put(e,PRESENT) will return old value ,if element is already present in that map. So  map.put(e, PRESENT) == null will return false, hence add method will return false and element will not be added in HashSet.

Please go through  core java interview questions for beginners for more interview questions.

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
This is 3rd part of java binary tree tutorial.

In this post, we will see about PostOrder binary tree traversal in java.

PostOrder traversal:

In PostOrder traversal,each node is processed after subtrees traversal.In simpler words,Visit left subtree,  right subtree and then node.

Steps for PostOrder traversal are:
  • Traverse the left subtree in PostOrder.
  • Traverse the right subtree in PostOrder.
  • Visit the node.
 There can be two ways of implementing it
  • Recursive
  • Iterative
Recursive solution:
Recursive solution is very straight forward.Below diagram will make you understand recursion better.

Code for recursion will be:
public void postOrder(TreeNode root) {
  if(root !=  null) {
   postOrder(root.left);
   postOrder(root.right);
   //Visit the node by Printing the node data  
   System.out.printf("%d ",root.data);
  }
 }
Iterative solution:
Steps for iterative solution:
  1. Create an empty stack s and set currentNode =root.
  2. while currentNode is not NULL Do following
    1. Push currentNode 's right child and then currentNode to stack.
    2. Set currentNode =currentNode .left
  3. Pop an node from stack and set it as root and set it to currentNode 
    1. If the popped node has a right child and the right child is at top of stack, then remove the right child from stack, push the current node back and set currentNode as currentNode 's right child.
    2. Else print currentNode 's data and set currentNode as NULL.
  4. Repeat steps 2 and 3 while stack is not empty.
 
 public void postorderIter( TreeNode root) {
      if( root == null ) return;
   
      Stack<TreeNode> s = new Stack<TreeNode>( );
      TreeNode current = root;
   
      while( true ) {
   
          if( current != null ) {
              if( current.right != null ) 
               s.push( current.right );
              s.push( current );
              current = current.left;
              continue;
        }
   
          if( s.isEmpty( ) ) 
           return;
          current = s.pop( );
   
          if( current.right != null && ! s.isEmpty( ) && current.right == s.peek( ) ) {
              s.pop( );
              s.push( current );
              current = current.right;
          } else {
              System.out.print( current.data + " " );
              current = null;
          }
      }
  }
Lets create java program for InOrder traversal:
 
package org.arpit.java2blog;

import java.util.Stack;

public class BinaryTree {

 
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
        // Recursive Solution
 public void postOrder(TreeNode root) {
  if(root !=  null) {
   postOrder(root.left);
   postOrder(root.right);
   //Visit the node by Printing the node data  
   System.out.printf("%d ",root.data);
  }
 }
 
  // Iterative solution
  public void postorderIter( TreeNode root) {
      if( root == null ) return;
   
      Stack<TreeNode> s = new Stack<TreeNode>( );
      TreeNode current = root;
   
      while( true ) {
   
          if( current != null ) {
              if( current.right != null ) 
               s.push( current.right );
              s.push( current );
              current = current.left;
              continue;
        }
   
          if( s.isEmpty( ) ) 
           return;
          current = s.pop( );
   
          if( current.right != null && ! s.isEmpty( ) && current.right == s.peek( ) ) {
              s.pop( );
              s.push( current );
              current = current.right;
          } else {
              System.out.print( current.data + " " );
              current = null;
          }
      }
  }
 
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Using Recursive solution:");

  bi.inOrder(rootNode);

  System.out.println();
  System.out.println("-------------------------");
  System.out.println("Using Iterative solution:");

  bi.inOrderIter(rootNode);
 }
 
 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);
  
  rootNode.left=node20;
  rootNode.right=node60;
  
  node20.left=node10;
  node20.right=node30;
  
  node60.left=node50;
  node60.right=node70;
  
  return rootNode;
 }
}

Run above program and you will get following output:
 
Using Recursive solution:
10 30 20 50 70 60 40 
-------------------------
Using Iterative solution:
10 30 20 50 70 60 40  

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.

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
This is 4th part of java binary tree tutorial.
In this post, we will see about InOrder binary tree traversal in java.

InOrder traversal:

In InOrder traversal,each node is processed between subtrees.In simpler words,Visit left subtree, node and then right subtree.
Steps for InOrder traversal are:
  • Traverse the left subtree in InOrder.
  • Visit the node.
  • Traverse the right subtree in InOrder.
 There can be two ways of implementing it
  • Recursive
  • Iterative
Recursive solution:
Recursive solution is very straight forward.Below diagram will make you understand recursion better.

Code for recursion will be:
public void inOrder(TreeNode root) {
  if(root !=  null) {
   inOrder(root.left);
   //Visit the node by Printing the node data  
   System.out.printf("%d ",root.data);
   inOrder(root.right);
  }
 }
Iterative solution:
For recursion, we use implicit stack. So here to convert recursive solution to iterative, we will use explicit stack.
Steps for iterative solution:
  1. Create an empty stack s and Initialize current node as root
  2. Push the current node to s and set currentNode = currentNode.left until currentNode is NULL
  3. If currentNode is NULL and s is not empty then
    • Pop the top node from stack and print it
    •  set currentNode = currentNode.right
    • go to step 2
  4. If stack is empty and currentNode is also null then we are done with it
 
public void inOrderIter(TreeNode root) {

  if(root == null)
   return;

  Stack<TreeNode> s = new Stack<TreeNode>();
  TreeNode currentNode=root;

  while(!s.empty() || currentNode!=null){

   if(currentNode!=null)
   {
    s.push(currentNode);
    currentNode=currentNode.left;
   }
   else
   {
    TreeNode n=s.pop();
    System.out.printf("%d ",n.data);
    currentNode=n.right;
   }
  }
 }

Lets create java program for InOrder traversal:
 
package org.arpit.java2blog;

import java.util.Stack;

public class BinaryTree {

 
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
        // Recursive Solution
 public void inOrder(TreeNode root) {
  if(root !=  null) {
   inOrder(root.left);
   //Visit the node by Printing the node data  
   System.out.printf("%d ",root.data);
   inOrder(root.right);
  }
 }
 
  // Iterative solution
 public void inOrderIter(TreeNode root) {

  if(root == null)
   return;

  Stack<TreeNode> s = new Stack<TreeNode>();
  TreeNode currentNode=root;

  while(!s.empty() || currentNode!=null){

   if(currentNode!=null)
   {
    s.push(currentNode);
    currentNode=currentNode.left;
   }
   else
   {
    TreeNode n=s.pop();
    System.out.printf("%d ",n.data);
    currentNode=n.right;
   }
  }
 }
 
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Using Recursive solution:");

  bi.inOrder(rootNode);

  System.out.println();
  System.out.println("-------------------------");
  System.out.println("Using Iterative solution:");

  bi.inOrderIter(rootNode);
 }
 
 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);
  
  rootNode.left=node20;
  rootNode.right=node60;
  
  node20.left=node10;
  node20.right=node30;
  
  node60.left=node50;
  node60.right=node70;
  
  return rootNode;
 }
}
Run above program and you will get following output:
 
Using Recursive solution:
10 20 30 40 50 60 70 
-------------------------
Using Iterative solution:
10 20 30 40 50 60 70  

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.

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
This is 2nd part of java binary tree tutorial.

In this post, we will see about PreOrder binary tree traversal in java.

PreOrder traversal:

In PreOrder traversal,each node is processed before either of its sub-trees.In simpler words,Visit each node before its children.

Steps for PreOrder traversal are:
  • Visit the node.
  • Traverse the left subtree in PreOrder.
  • Traverse the right subtree in PreOrder.
 There can be two ways of implementing it
  • Recursive
  • Iterative
Recursive solution:
Recursive solution is very straight forward.Below diagram will make you understand recursion better.



Code for recursion will be:

public void preorder(TreeNode root) {
    if(root !=  null) {
   //Visit the node by Printing the node data  
      System.out.printf("%d ",root.data);
      preorder(root.left);
      preorder(root.right);
    }
  }
Iterative solution:
For recursion, we use implicit stack. So here to convert recursive solution to iterative, we will use explicit stack.
Steps for iterative solution:
  1. Create empty stack and pust root node to it.
  2. Do the following when stack is not empty
    • Pop a node from stack and print it
    • Push right child of popped node to stack
    • Push left child of popped node to stack
We are pushing right child first, so it will be processed after left subtree as Stack is LIFO.
 
public void preorderIter(TreeNode root) {
   
         if(root == null)
             return;
  
         Stack<TreeNode> stack = new Stack<TreeNode>();
         stack.push(root);
  
         while(!stack.empty()){
          
             TreeNode n = stack.pop();
             System.out.printf("%d ",n.data);
  
           
             if(n.right != null){
                 stack.push(n.right);
             }
             if(n.left != null){
                 stack.push(n.left);
             }
  
         }
         
     }

Example:
Lets say your binary tree is :

Lets create java program for PreOrder traversal:
 
package org.arpit.java2blog;

import java.util.Stack;

public class BinaryTree {

 
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
        // Recursive Solution
 public void preorder(TreeNode root) {
    if(root !=  null) {
   //Visit the node-Printing the node data  
      System.out.printf("%d ",root.data);
      preorder(root.left);
      preorder(root.right);
    }
  }
 
  // Iterative solution
  public void preorderIter(TreeNode root) {
   
         if(root == null)
             return;
  
         Stack<TreeNode> stack = new Stack<TreeNode>();
         stack.push(root);
  
         while(!stack.empty()){
          
             TreeNode n = stack.pop();
             System.out.printf("%d ",n.data);
  
           
             if(n.right != null){
                 stack.push(n.right);
             }
             if(n.left != null){
                 stack.push(n.left);
             }
  
         }
         
     }
 
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Using Recursive solution:");
  
  bi.preorder(rootNode);
  
  System.out.println();
  System.out.println("-------------------------");
  System.out.println("Using Iterative solution:");
  
  bi.preorderIter(rootNode);
 }
 
 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);
  
  rootNode.left=node20;
  rootNode.right=node60;
  
  node20.left=node10;
  node20.right=node30;
  
  node60.left=node50;
  node60.right=node70;
  
  return rootNode;
 }
}

Run above program and you will get following output:
 
Using Recursive solution:
40 20 10 30 60 50 70
-------------------------
Using Iterative solution:
40 20 10 30 60 50 70 

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.

One of the common interview question is "What is difference between sleep and wait in java".Before we actually see differences,let me give you brief introduction of both.

sleep

  • It causes current executing thread to sleep for specific amount of time.
  • Its accuracy depends on system timers and schedulers.
  • It keeps the monitors it has acquired, so if it is called from synchronized context, no other thread can enter that block or method.
  • If we call interrupt() method , it will wake up the sleeping thread.
    synchronized(lockedObject) {   
      Thread.sleep(1000); // It does not release the lock on lockedObject.
      // So either after 1000 miliseconds, current thread will wake up, or after we call 
      //t. interrupt() method.
      
  }

wait

  • It causes current thread to wait until either another thread invokes the notify() method or the notifyAll() method for this object
  • It must be called from synchronized context i.e. from block or method.It means before wait() method is called,current thread must have lock on that object.
  • It releases lock on the object on which it is called and added to wait list, so another thread can acquire lock on the object.
    synchronized(lockedObject) {   
   lockedObject.wait(); // It releases the lock on lockedObject.
      // So until we call notify() or notifyAll() from other thread,It will
   // not wake up
      
  }

sleep vs wait:

Parameter
wait
sleep
Synchonized
wait should be called from synchronized context i.e. from block or method, If you do not call it using synchronized context, it will throw IllegalMonitorStateException

It need not be called from synchronized block or methods
Calls on
wait method operates on Object and defined in Object class

Sleep method operates on current thread and is in java.lang.Thread
Release of lock
wait release lock of object on which it is called and also other locks if it holds any
Sleep method does not release lock at all
Wake up condition
until call notify() or notifyAll() from Object class
Until time expires or calls interrupt()
static
wait is non static method
sleep is static method
You can go through core java interview questions for beginners and experienced for more such questions.

In this post, we will see how to find prime factors of a number in java.
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
The prime factors of a number are all of the prime numbers that will exactly divide the given number.
For example-
Prime factor of 15 = 3,5
Prime factor of 48=2,2,2,2,3

Lets create java program for it:
package org.arpit.java2blog;

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

public class PrimeFactorsMain {

 // This method calculate prime factor and add it to primeFactor list
 public static List<Integer> primeFactors(int number) {
  int n = number;
  List<Integer> primeFactors = new ArrayList<Integer>();
  for (int i = 2; i <= n; i++) {
   while (n % i == 0) {
    primeFactors.add(i);
    n /= i;
   }
  }
  return primeFactors;
 }

 public static void main(String[] args) {
  System.out.println("Primefactors of 15 are : ");
  System.out.printf("%s %n",primeFactors(15));

  System.out.println("Primefactors of 48 are :");
  System.out.printf("%s %n",primeFactors(48));

  System.out.println("Primefactors of 91");
  System.out.printf("%s %n",primeFactors(91));

 }
} 
Run above program and you will get following output:
Primefactors of 15 are : 
[3, 5] 
Primefactors of 48 are :
[2, 2, 2, 2, 3] 
Primefactors of 91
[7, 13] 
You must be wondering we are not checking whether loop variable i is prime or not But you don't need to do this because in any loop, number has been already divided by 2 to i-1 so i can only be divisor if it is prime.

More optimized solution:

Change above primeFactors function to below function
 // This method calculate prime factor and add it to primeFactor list
 public static List<Integer> primeFactors(int number) {
  int n = number;
  List<Integer> primeFactors = new ArrayList<Integer>();
  for (int i = 2; i <= n/i; i++) {
   while (n % i == 0) {
    primeFactors.add(i);
    n /= i;
   }
  }
  if(n>1)
   primeFactors.add(n);
  return primeFactors;
 } 
This is based on the fact that in above for loop,divisor can not be greater than n/i.

Please go through java interview programs for more such programs.

A palindrome is a word, phrase, number, or other sequence of symbols or elements that reads the same forward or reversed. 
For example: 12121 is palindrome as it reads same forward or reversed. madam is also a palindrome .
This is very simple interview question.There are many ways to check if given string is palindrome or not.

Reversing a String and then comparing it with input String:

package org.arpit.java2blog;
import java.util.Scanner;

public class StringFullLoopPalindrome {


 public static void main(String[] args) {

  Scanner scanner = new Scanner(System.in);
  System.out.print("Enter string : ");

  String str = scanner.nextLine();
  String reverseStr = "";

  for(int i = str.length() - 1; i >= 0; i--){
   reverseStr = reverseStr + str.charAt(i);
  }

  if(str.equals(reverseStr)){
   System.out.println("String is palindrome");
  } else {
   System.out.println("String is not palindrome");
  }
 }
}

Run above program, you will get following output:
Enter string : 12121
String is palindrome
Enter a string : Apple
String is not palindrome

Using half loop,Moving from both end of String simultaneously:

package org.arpit.java2blog;
import java.util.Scanner;

public class StringUsingHalfLoop {

 public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in);
  System.out.print("Enter a string : ");

  String str = scanner.nextLine();
  boolean isPalin=isPalindrome(str);
  if(isPalin)
   System.out.println("String is Palindrome");
  else
   System.out.println("String is not Palindrome");
  
 }

 static boolean isPalindrome(String str)
 {
  for (int i = 0,j=str.length()-1; i <str.length()/2; i++,j--) {

   if(str.charAt(i)!=str.charAt(j))
   {
    return false;
   }

  }
  return true;
 }

}
 
Run above program, you will get following output:
Enter a string : madam
String is Palindrome
Enter a string : adam
String is not Palindrome

Using StringBuilder's reverse() function:

package org.arpit.java2blog;

import java.util.Scanner;

public class StringPalindrome {

 public static void main(String[] args) {
   Scanner scanner = new Scanner(System.in);
      System.out.print("Enter string : ");
           
      String str = scanner.nextLine();
      StringBuilder strBuilder = new StringBuilder(str);
           
      strBuilder.reverse();
           
      if(str.equals(strBuilder.toString())){
          System.out.println("String is palindrome");
      } else {
          System.out.println("String is not palindrome");
      }

 }

}
Run above program, you will get following output:
Enter a string : stats
String is palindrome
Enter a string : 1212121
String is palindrome

Please go through java interview programs for more such programs.

This is easy question. It may not be asked you directly, but you can use this program to create many other complex program.
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. 

Program logic: 

If any number which is not divisible by any other number which is less than or equal to square root of that number, then it is prime number.
Lets create java program for it:
package org.arpit.java2blog;

public class PrimeNumberMain {

 public static void main(String[] args) {
   
  System.out.println("17 is prime number?: "+isPrime(17));
  System.out.println("2 is prime number?: "+isPrime(2));
  System.out.println("91 is prime number?: "+isPrime(91));
  System.out.println("29 is prime number?: "+isPrime(29));
  System.out.println("81 is prime number?: "+isPrime(81));
 }
 
 public static boolean isPrime(int number)
 {
  for (int i = 2; i <=Math.sqrt(number); i++) {
   if(number%i==0)
    return false;
  }
  return true;
 }

}
Run above program, you will get following output:
17 is prime number?: true
2 is prime number?: true
91 is prime number?: false
29 is prime number?: true
81 is prime number?: false

Please go through java interview programs for more such programs.

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
This is one of popular interview question.

Java Linked List Interview Programs:

    How to detect a loop in linked list in java Find start node of loop in linkedlist How to find middle element of linked list in java How to find nth element from end of linked list How to reverse a linked list in java Add two numbers represented by linked list in java
There can be two solution for reversing linked list
  • Iterative
  • Recursive

Iterative:

Logic for this would be:
  • Have three nodes i.e previousNode,currentNode and nextNode
  • When currentNode is starting node, then previousNode will be null
  • Assign currentNode.next to previousNode to reverse the link.
  • In each iteration move currentNode and previousNode by  1 node.
public static Node reverseLinkedList(Node currentNode)
 {
// For first node, previousNode will be null
Node previousNode=null;
  Node nextNode;
  while(currentNode!=null)
  {
   nextNode=currentNode.next;
  // reversing the link
   currentNode.next=previousNode;
  // moving currentNode and previousNode by 1 node
   previousNode=currentNode;
   currentNode=nextNode;
  }
  return previousNode;
 }
Java program for this will be :
package org.arpit.java2blog;

public class LinkedList{

 private Node head;

 private static class Node {
  private int value;
  private Node next;

  Node(int value) {
   this.value = value;

  }
 }

 public void addToTheLast(Node node) {

  if (head == null) {
   head = node;
  } else {
   Node temp = head;
   while (temp.next != null)
    temp = temp.next;

   temp.next = node;
  }
 }


 public void printList(Node head) {
  Node temp = head;
  while (temp != null) {
   System.out.format("%d ", temp.value);
   temp = temp.next;
  }
  System.out.println();
 }

 // Reverse linkedlist using this function 
public static Node reverseLinkedList(Node currentNode)
 {
// For first node, previousNode will be null
Node previousNode=null;
  Node nextNode;
  while(currentNode!=null)
  {
   nextNode=currentNode.next;
  // reversing the link
   currentNode.next=previousNode;
  // moving currentNode and previousNode by 1 node
   previousNode=currentNode;
   currentNode=nextNode;
  }
  return previousNode;
 }

 public static void main(String[] args) {
  LinkedList list = new LinkedList();
  // Creating a linked list
  Node head=new Node(5);
  list.addToTheLast(head);
  list.addToTheLast(new Node(6));
  list.addToTheLast(new Node(7));
  list.addToTheLast(new Node(1));
  list.addToTheLast(new Node(2));
 
  list.printList(head);
  //Reversing LinkedList
  Node reverseHead=reverseLinkedList(head);
  System.out.println("After reversing");
  list.printList(reverseHead);
 
 }

}

Run above program, you will get following output:
5 6 7 1 2 
After reversing
2 1 7 6 5 

Recursive:

Base case: Base case for this would be either node is null or node.next is null
For recursive solution, replace reverseLinkedList of above program to below function
public static Node reverseLinkedList(Node node) {
     if (node == null || node.next == null) {
         return node;
     }

     Node remaining = reverseLinkedList(node.next);
     node.next.next = node;
     node.next = null;
    return remaining;
 }
Output of this program will be same as above program.
Now lets understand logic for above recursive program.
5->6->7->1->2
Above function will terminate when last node(2) 's next will be null.so while returning when you reach at node with value 1,If you closely observe node.next.next=node is actually setting 2->1(i.e. reversing the link between node with value 1 and 2) and node.next=null is removing link 1->2. So in each iteration, you are reversing link between two nodes.
Below diagram will make it clear


Please go through java interview programs for more such programs.

This is one of popular interview question.

Java Linked List Interview Programs:

    How to reverse a linked list in java How to reverse a linked list in pairs in java How to find middle element of linked list in java How to detect a loop in linked list in java Find start node of loop in linkedlist How to find nth element from end of linked list How to check if linked list is palindrome in java Add two numbers represented by linked list in java

Assumption:

We do not know size of linkedlist otherwise we can directly iterate and find (length-n)th node

Algorithm for this problem would be :

  • Use two pointer firstPtr and secondPtr and initialize both to head of linkedlist
  • Move firstPtr by n-1 nodes.
  • Increment firstPtr and secondPtr until firstPtr.next not equal to null.
  • SecondPtr will be at nth from end node.
Java program for this will be :
package org.arpit.java2blog;

public class LinkedList{

 private Node head;

 private static class Node {
  private int value;
  private Node next;

  Node(int value) {
   this.value = value;

  }
 }

 public void addToTheLast(Node node) {

  if (head == null) {
   head = node;
  } else {
   Node temp = head;
   while (temp.next != null)
    temp = temp.next;

   temp.next = node;
  }
 }


 public void printList() {
  Node temp = head;
  while (temp != null) {
   System.out.format("%d ", temp.value);
   temp = temp.next;
  }
  System.out.println();
 }

 
 public Node nthFromLastNode(Node head,int n)
 {
  Node firstPtr=head;
  Node secondPtr=head;
  
  for (int i = 0; i < n; i++) {
   firstPtr=firstPtr.next;
   
  }
  
  while(firstPtr!=null)
  {
   firstPtr=firstPtr.next;
   secondPtr=secondPtr.next;
  }
  
  return secondPtr;
 }
 
 public static void main(String[] args) {
  LinkedList list = new LinkedList();
  // Creating a linked list
  Node head=new Node(5);
  list.addToTheLast(head);
  list.addToTheLast(new Node(6));
  list.addToTheLast(new Node(7));
  list.addToTheLast(new Node(1));
  list.addToTheLast(new Node(2));
 
  list.printList();
  // Finding 3rd node from end
  Node nthNodeFromLast= list.nthFromLastNode(head,3);
  System.out.println("3th node from end is : "+ nthNodeFromLast.value);

 }

}

Logically our linkedlist look like following:


Color node represent 3rd node from last.
Run above program, you will get following output:
5 6 7 1 2 
3th node from end is : 7

Please go through java interview programs for more such programs.

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
This is one of the popular interview question.
In this post, we will discuss how to find middle element in linkedlist in most efficient way.

Java Linked List Interview Programs:

    How to reverse a linked list in java How to reverse a linked list in pairs in java How to find middle element of linked list in java How to detect a loop in linked list in java Find start node of loop in linkedlist How to find nth element from end of linked list How to check if linked list is palindrome in java Add two numbers represented by linked list in java

Assumption:

I am not using java LinkedList API here. If you use that API, you can directly find size of linkedlist using size() function and then locate length/2.

One of the algo for this would be:

  • Traverse the list and find the length of list
  • After finding length, again traverse the list and locate n/2 element from head of linkedlist.
Time complexity=time for finding length of list + time for locating middle element=o(n)+o(n) =o(n)
Space complexity= o(1).

Efficient approach:

Above approach will take two traversal but we can find middle element in one traversal also using following algo:
  1. Use two pointer fastptr and slowptr and initialize both to head of linkedlist
  2. Move fastptr by two nodes and slowptr by one node in each iteration.
  3. When fastptr reaches end of nodes, the slowptr pointer will be  pointing to middle element.
 Lets create java program for it:
package org.arpit.java2blog;

public class LinkedList{

 private Node head;

 private static class Node {
  private int value;
  private Node next;

  Node(int value) {
   this.value = value;

  }
 }

 public void addToTheLast(Node node) {

  if (head == null) {
   head = node;
  } else {
   Node temp = head;
   while (temp.next != null)
    temp = temp.next;

   temp.next = node;
  }
 }


 public void printList() {
  Node temp = head;
  while (temp != null) {
   System.out.format("%d ", temp.value);
   temp = temp.next;
  }
  System.out.println();
 }

// This function will find middle element in linkedlist
 public Node findMiddleNode(Node head)
 {
 Node slowPointer, fastPointer; 
  slowPointer = fastPointer = head; 

  while(fastPointer !=null) { 
   fastPointer = fastPointer.next; 
   if(fastPointer != null && fastPointer.next != null) { 
    slowPointer = slowPointer.next; 
    fastPointer = fastPointer.next; 
   } 
  } 

  return slowPointer; 

 }

 public static void main(String[] args) {
  LinkedList list = new LinkedList();
  // Creating a linked list
  Node head=new Node(5);
  list.addToTheLast(head);
  list.addToTheLast(new Node(6));
  list.addToTheLast(new Node(7));
  list.addToTheLast(new Node(1));
  list.addToTheLast(new Node(2));
 
  list.printList();
  // finding middle element
  Node middle= list.findMiddleNode(head);
  System.out.println("Middle node will be: "+ middle.value);

 }

}
Logically linked list can be represented as:



Middle element is represented in red color.
Run above program, you will get following output:
5 6 7 1 2 
Middle node is: 7

Please go through java interview programs for more such programs.

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
One of the most popular interview question nowadays is "How to detect loop/cycle in LinkedList". So I thought I should cover this question. This question is more related to data structure. You can also find start node of loop if loop exists.

Java Linked List Interview Programs:

    How to reverse a linked list in java How to reverse a linked list in pairs in java How to find middle element of linked list in java How to detect a loop in linked list in java Find start node of loop in linkedlist How to find nth element from end of linked list How to check if linked list is palindrome in java Add two numbers represented by linked list in java

First approach that you may think may something look like:
  • Traverse through each node till end , tracking visited node using visited flag.
  • If you find node that is already visited, then there is a loop in LinkedList and if you reach till end while traversing then there is no loop in LinkedList
But problem with above approach is, in most cases you can not change data structure of LinkedList node, so you won't be able to add visited flag to it.

Efficient approach:

Efficient approach for this problem would be Floyd's cycle detection algorithm,so steps for this algo would be:
  • Use two pointer fastPtr and slowPtr and initialize both to head of linkedlist
  • Move fastPtr by two nodes and slowPtr by one node in each iteration.
  • If fastPtr and slowPtr meet at some iteration , then there is a loop in linkedlist.
  • If fastPtr reaches to the end of linkedlist without meeting slow pointer then there is no loop in linkedlist (i.e fastPtr->next or fastPtr->next->next become null)

Java code for this algo will be 
 public boolean ifLoopExists() {
  Node fastPtr = head;
  Node slowPtr = head;
  while (fastPtr != null && fastPtr.next != null) {
   fastPtr = fastPtr.next.next;
   slowPtr = slowPtr.next;
   if (slowPtr == fastPtr)
    return true;

  }
  return false;
 }
Above solution work with o(n) time complexity and o(1) space complexity.

Lets create linked list without loop :

Lets create a java program called "LinkedList.java"

package org.arpit.java2blog;

public class LinkedList{

 private Node head;

 private static class Node {
  private int value;
  private Node next;

  Node(int value) {
   this.value = value;
  
  }
 }

 public void addToTheLast(Node node) {
  
  if (head == null) {
   head = node;
  } else {
   Node temp = head;
   while (temp.next != null)
    temp = temp.next;

   temp.next = node;
  }
 }

 
 public void printList() {
  Node temp = head;
  while (temp != null) {
   System.out.format("%d ", temp.value);
   temp = temp.next;
  }
  System.out.println();
 }

 public boolean ifLoopExists() {
  Node fastPtr = head;
  Node slowPtr = head;
  while (fastPtr != null && fastPtr.next != null) {
   fastPtr = fastPtr.next.next;
   slowPtr = slowPtr.next;
   if (slowPtr == fastPtr)
    return true;

  }
  return false;
 }

 public static void main(String[] args) {
  LinkedList list = new LinkedList();
  // Creating a linked list
  
  list.addToTheLast(new Node(5));
  list.addToTheLast(new Node(6));
  list.addToTheLast(new Node(7));
  list.addToTheLast(new Node(1));
  list.addToTheLast(new Node(2));
  
  
  list.printList();
  
    // Test if loop existed or not
  System.out.println("Loop existed-->" + list.ifLoopExists());

 }
}

Logically our linkedlist can be represented as :



Run above program, you will get following output:
5 6 7 1 2 
Loop existed-->false

Lets create a loop in linkedlist

Now we will connect last node to the nodewith value 7 and it will create loop in linked list, so change above main method to this:
public static void main(String[] args) {
  LinkedList list = new LinkedList();
  // Creating a linked list
  Node loopNode=new Node(7);
  list.addToTheLast(new Node(5));
  list.addToTheLast(new Node(6));
  list.addToTheLast(loopNode);
  list.addToTheLast(new Node(1));
  list.addToTheLast(new Node(2));
  
  list.printList();
  // creating a loop
  list.addToTheLast(loopNode);
    // Test if loop existed or not
  System.out.println("Loop existed-->" + list.ifLoopExists());

 }
Logically our linkedlist with loop can be represented as :



Run above program, you will get following output:
5 6 7 1 2 
Loop existed-->true
so this is how you can detect a loop in linkedlist.

Please go through java interview programs for more such programs.
 

Java tutorial for beginners Copyright © 2012