Monday, 4 August 2014

Binary tree in java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child

Example of binary tree:

I have posted various programs on binary tree so that you can practice them for interviews and it will also help in understanding recursion.

Binary tree traversals:

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

InOrder traversal : In InOrder traversal,each node is processed between subtrees.In simpler words,Visit left subtree, node and then right subtree.

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

Level order traversal : In Level order traversal, tree is traversed by each level. It is same as breadth first search.

Spiral/Zigzag order traversal : In spiral order traversal, tree is traversed in spiral shape.

Other Binary tree programs:




print all paths from root to leaf in a binary tree in java

In this post, we will see about program to print all paths from root to leaf in a binary tree in java.
Below diagram will show all paths  from root to leaf:

Algorithm:

Steps for print all paths from root to leaf are:
  • If node is null then return 0
  • put node.data in array and increment len by 1.
  • If encounterd leaf node(i.e. node.left is null and node.right is null) then print array.
  • Recursively visit left subtree and right subtree

Code for recursion will be:
// Prints all paths to leaf
 public static void printAllPathsToLeaf(TreeNode node, int[] path, int len) {
     if ( node == null )
         return;

     // storing data in array
     path[len] = node.data;
     len++;

     if(node.left == null && node.right == null) {
         // leaf node is reached
         printArray(path,len);
         return;
     }

     printAllPathsToLeaf(node.left, path, len);
     printAllPathsToLeaf(node.right, path, len);
 }


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;
  }
 }
 
// Prints all paths to leaf
 public static void printAllPathsToLeaf(TreeNode node, int[] path, int len) {
     if ( node == null )
         return;

     // storing data in array
     path[len] = node.data;
     len++;

     if(node.left == null && node.right == null) {
         // leaf node is reached
         printArray(path,len);
         return;
     }

     printAllPathsToLeaf(node.left, path, len);
     printAllPathsToLeaf(node.right, path, len);
 }

 
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Printing all paths from root to leaf :");
  printAllPathsToLeaf(rootNode,new int[1000],0);
 }
 
 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 all paths from root to leaf :
40 20 10 5 
40 20 30 
40 60 50 55 
40 60 70 

Spiral/Zigzag level order traversal of binary tree in java

In this post, we will see about Spiral/Zigzag Level Order binary tree traversal in java.

Spiral/Zigzag Level Order traversal:

 Spiral/Zigzag Level order traversal of below tree will be:


Steps for solution:
  1. Create an empty stack s and push root to it.
  2. while stack is not NULL Do following
    1. Create a empty stack called tempStack.
    2. Pop a node from stack and push it to tempStack depending on directionFlag
    3. Change directionFlag to change the direction of traversal
    4. set stack=tempStack
 
// prints in Spiral/Zigzag level order
 public static void spiralOrZigzagLevelOrder(TreeNode root) {
        if(root==null) return; 
        Stack<TreeNode> stack=new Stack<TreeNode>();
        stack.push(root);
        
        boolean directionflag=false;
        while(!stack.isEmpty())
        {
            Stack<TreeNode> tempStack=new Stack<TreeNode>();
        
            while(!stack.isEmpty())
            {
                TreeNode tempNode=stack.pop();
             System.out.printf("%d ",tempNode.data);
                if(!directionflag) 
                {
                    if(tempNode.left!=null) 
                     tempStack.push(tempNode.left);
                    if(tempNode.right!=null) 
                     tempStack.push(tempNode.right);
                }else
                {
                    if(tempNode.right!=null) 
                     tempStack.push(tempNode.right);
                    if(tempNode.left!=null) 
                     tempStack.push(tempNode.left);
                }
            }
            // for changing direction
            directionflag=!directionflag; 
      
            stack=tempStack; 
        }
     
    }

Example:
Lets say your binary tree is :


So Spiral/Zigzag Level Order traversal will work as below:

Lets create java program for Spiral/Zigzag Level 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 spiral/zigzag level order
 public static void spiralOrZigzagLevelOrder(TreeNode root) {
        if(root==null) return; 
        Stack<TreeNode> stack=new Stack<TreeNode>();
        stack.push(root);
        
        boolean directionflag=false;
        while(!stack.isEmpty())
        {
            Stack<TreeNode> tempStack=new Stack<TreeNode>();
        
            while(!stack.isEmpty())
            {
                TreeNode tempNode=stack.pop();
             System.out.printf("%d ",tempNode.data);
                if(!directionflag) 
                {
                    if(tempNode.left!=null) 
                     tempStack.push(tempNode.left);
                    if(tempNode.right!=null) 
                     tempStack.push(tempNode.right);
                }else
                {
                    if(tempNode.right!=null) 
                     tempStack.push(tempNode.right);
                    if(tempNode.left!=null) 
                     tempStack.push(tempNode.left);
                }
            }
            // for changing direction
            directionflag=!directionflag; 
      
            stack=tempStack; 
        }
     
    }
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Spiral/Zigzag traversal of binary tree :");
  spiralOrZigzagLevelOrder(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:
 
Spiral/Zigzag traversal of binary tree :
40 60 20 10 30 50 70 55 5 

Sunday, 20 July 2014

program to count leaf nodes in a 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 encounterd 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

how to print leaf nodes of a binary tree in java

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 

Saturday, 19 July 2014

Binary Tree Level Order traversal 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 PreOrder 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 

How HashSet works 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.

Thursday, 17 July 2014

Binary Tree PostOrder traversal in java

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  

Tuesday, 15 July 2014

Binary Tree InOrder traversal in java

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  

Binary Tree PreOrder traversal in java

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 

Friday, 11 July 2014

Difference between sleep and wait in java


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

Thursday, 10 July 2014

How to find prime factors of a number in java

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.

Wednesday, 9 July 2014

Java program to check Palindrome

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
 

Java tutorial for beginners Copyright © 2012