RAW JAVA - Java Programs

Familiarisation of java lists

noreply@blogger.com (Anonymous) — Tue, 26 May 2015 10:10:00 +0000

What are Lists?

The java.util.List interface is a subtype of the java.util.Collection interface.
The List interface extends Collection and declares the behavior of a collection that stores a sequence of elements.

Elements can be inserted or accessed by their position in the list, using a zero-based index.
A list may contain duplicate elements.
In addition to the methods defined by Collection, List defines some of its own, which are summarized in the following below Table.
Several of the list methods will throw an UnsupportedOperationException if the collection cannot be modified, and a ClassCastException is generated when one object is incompatible with another.

How to initialise?

Since List is an interface you need to instantiate a concrete implementation of the interface in order to use it. You can choose between the following List implementations in the Java Collections API:

java.util.ArrayList
java.util.LinkedList
java.util.Vector
java.util.Stack

We can instantiate lists with above as:

List<E> AL = new ArrayList<>();
List<E> LL= new LinkedList<>();
List<E> V = new Vector<>();
List<E> S = new Stack<>();

We should give the generic class otherwise there would be unchecked/unsafe operation error. generic classes can be any predefined or user defined classes.

As with standard linked list and array operations, the various methods will have different algorithmic runtimes.
For LinkedList<E>

get(int index) is O(n)
add(E element) is O(1)
add(int index, E element) is O(n)
remove(int index) is O(n)
Iterator.remove() is O(1) <--- main benefit of LinkedList<E>
ListIterator.add(E element) is O(1) <--- main benefit of LinkedList<E>

For ArrayList<E>

get(int index) is O(1) <--- main benefit of ArrayList<E>
add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
add(int index, E element) is O(n - index) amortized, but O(n) worst-case (as above)
remove(int index) is O(n - index) (i.e. removing last is O(1))
Iterator.remove() is O(n - index)
ListIterator.add(E element) is O(n - index)

How to add elements?

List interface supports these functions for adding elements

void add(E obj)

Adds objects to the end of the list.

void add(int index,E obj)

Inserts obj into the invoking list at the index passed in index. Any pre-existing elements at or beyond the point of insertion are shifted up. Thus, no elements are overwritten.

boolean addAll(int index, Collection c)

Inserts all elements of c into the invoking list at the index passed in index. Any pre-existing elements at or beyond the point of insertion are shifted up. Thus, no elements are overwritten. Returns true if the invoking list changes and returns false otherwise.

Here are a few examples:

List<Integer> AL = new ArrayList<>();
AL.add(0);
AL.add(5);//adding elements at the end of list
AL.add(1,4);// adding elements at a specified index
List<Integer> tmp = new LinkedList<>();
tmp.add(1);
tmp.add(2);
tmp.add(3);
AL.addAll(1,tmp);// adding an another collection

System.out.println(AL);
//Now the above statement yields output
[0, 1, 2, 3, 4, 5]

How to access elements?

The functions used to access elements are:

E get(int index)

Returns the object stored at the specified index within the invoking collection.

ListIterator listIterator( )

Returns an iterator to the start of the invoking list.

ListIterator listIterator(int index)

Returns an iterator to the invoking list that begins at the specified index.

The order in which the elements are added to the List is stored, so you can access the elements in the same order. You can do so using either the get(int index) method, or via the Iterator returned by the iterator() method. Here is how:

List listA = new ArrayList();

listA.add("element 0");
listA.add("element 1");
listA.add("element 2");

//access via index
String element0 = listA.get(0);
String element1 = listA.get(1);
String element3 = listA.get(2);


//access via Iterator
Iterator iterator = listA.iterator();
while(iterator.hasNext(){
  String element = (String) iterator.next();
}


//access via new for-loop
for(E object : listA) {
    String element = (String) object;
}

When iterating the list via its Iterator or via the for-loop (which also uses the

Iterator behind the scene), the elements are iterated in the same sequence they

are stored in the list.

How to delete elements?

These functions are used to remove elements:

remove(E element)

remove(E element) removes that element in the list, if it is present. All subsequent elements in the list are then moved up in the list. Their index thus decreases by 1.

remove(int index)

remove(int index) removes the element at the given index. All subsequent elements in the list are then moved up in the list. Their index thus decreases by 1.

How to delete elements?

The list elements can be changed by the function E set(int index, E element) which replaces the element at the specified position in this list with the specified element

JAVA program to handle same function with different number of parameters

noreply@blogger.com (Anonymous) — Sat, 23 May 2015 17:04:00 +0000

In this post i would like show you a cool feature of java to handle functions with different parameter sets. For example if you want to find sum of a set of parameters which maybe 2or 3or400 you can use this feature instead of doing messy convertions to array.

public class threeDots{



    static void sumIt(int...x){

        int t=0;

        for(int i:x)

            t+=i;

        System.out.println(t);

    }



    public static void main(String[] args) {

        sumIt(1);

        sumIt(1,2);

        sumIt(1,2,3);

        sumIt(1,2,3,4);

        sumIt(1,2,3,4,5);

        sumIt(1,2,3,4,5,6);        

    }

}

Output:
1
3
6
10
15
21

JAVA program to implement Eller's algorithm to generate random maze

noreply@blogger.com (Anonymous) — Fri, 22 May 2015 10:50:00 +0000

Algorithm:

Eller's algorithm creates 'perfect' mazes, having only a single path between any two cells, one row at a time. The algorithm itself is incredibly fast, and far more memory efficient than other popular algorithms (such as Prim's and Kruskal's) requiring storage proportional to only a single row. This makes it possible to create mazes of indefinite length on systems with limited memory.

The algorithm is explained below:

Create the first row. No cells will be members of any set

Join any cells not members of a set to their own unique set

Create right-walls, moving from left to right:

Randomly decide to add a wall or not

If the current cell and the cell to the right are members of the same set, always create a wall between them. (This prevents loops)

If you decide not to add a wall, union the sets to which the current cell and the cell to the right are members.

Create bottom-walls, moving from left to right:

Randomly decide to add a wall or not. Make sure that each set has at least one cell without a bottom-wall (This prevents isolations)

If a cell is the only member of its set, do not create a bottom-wall
If a cell is the only member of its set without a bottom-wall, do not create a bottom-wall

Decide to keep adding rows, or stop and complete the maze

If you decide to add another row:

Output the current row
Remove all right walls
Remove cells with a bottom-wall from their set
Remove all bottom walls
Continue from Step 2

If you decide to complete the maze

Add a bottom wall to every cell
Moving from left to right:

If the current cell and the cell to the right are members of a different set:

Remove the right wall
Union the sets to which the current cell and cell to the right are members.
Output the final row

CODE:

// a utility class to represent single cell
import java.util.*;

public class Cel{
 public boolean right,down;
 
 public List<Cel> set;
 
 public int x,y;
 
 Cel(int a,int b){
  
  x=a;
  
  y=b;
  
  right=false;
  
  down=true;
  
  set=null;
  
 }
 
}
// class to implement the algorithm
import java.util.*;



public class maze{
 
 static Random randomizer = new Random();
 
 static int size;
 
 static int[][] maze;
 
 static Scanner in = new Scanner(System.in);
 
 
 
 /*  Step 2: Grouping ungrouped cells to form new sets    */
 
 static Cel[] makeSet(Cel[] row) {
  
  for(int index = 0; index < row.length; ) {
   
   Cel cell = row[index++];
   
   if(cell.set == null) {
    
    List<Cel> list = new ArrayList<Cel>();
    
    list.add(cell);
    
    cell.set=list;
    
   }
   
  }
  
  return row;
  
 }
 
 /*********************************************************/
 
 
 
 /*  Step 3: Creating right walls                         */
 
 static Cel[] makeRightWalls(Cel[] row) {
  
  for(int i = 1; i < row.length; i++) {
   
   if(isContainsInList(row[i-1].set,row[i])) {
    
    row[i-1].right=true;
    
    continue;
    
   }
   
   if(randomizer.nextBoolean())
   
   row[i-1].right=true;
   
   else
    
   row=merge(row,i);
   
  }
  
  return row;
  
 }
 
 
 
 static Cel[] merge(Cel[] row,int i) {  //utility function
  
  List<Cel> currentList = row[i-1].set;
  
  List<Cel> nextList = row[i].set;
  
  for(Cel j : nextList) {
   
   currentList.add(j);
   
   j.set=currentList;
   
  }
  
  return row;
  
 }
 
 
 
 static boolean isContainsInList(List<Cel> set,Cel cell) {  //utility function
  
  for(Cel i : set) {
   
   if(i==cell)
   
   return true;
   
  }
  
  return false;
  
 }
 
 /*********************************************************/
 
 
 
 /*  Step 4: Creating down walls                          */
 
 static boolean isNotDone(List<Cel> set){    //utility function
  
  boolean rslt=true;
  
  for(Cel x:set)
  
  rslt=rslt&&x.down;
  
  return rslt;
  
 }
 
 
 
 static Cel[] makeDown(Cel[] row){
  
  for(int i=0;i<row.length;i++){
   
   for(Cel x:row[i].set)x.down=true;
   
   while(isNotDone(row[i].set)){
    
    do{
     
     row[i].set.get(randomizer.nextInt(row[i].set.size())).down=false;
     
    }while(randomizer.nextBoolean() || );
    
   }
   
  }
  
  return row;
  
 }
 
 /*********************************************************/
 
 
 
 /*  Driver function to execute the algorithm             */
 
 static public void driver(){
  
  System.out.print("Enter size: ");
  
  size=in.nextInt();
  
  maze=new int[2*size+1][2*size+1];
  
  Cel[] cur=new Cel[size];
  
  for(int i=0;i<size;i++)
  
  cur[i]=new Cel(0,i);
  
  for(int i=2;i<=2*size;i++)
  
  for(int j=2;j<=2*size;j++)
  
  maze[i][j]=0;
  
  for(int i=0;i<size;i++){
   
   cur=makeSet(cur);
   
   cur=makeRightWalls(cur);
   
   cur=makeDown(cur);
   
   if(i==size-1)
   
   cur=end(cur);
   
   printMaze(cur,i);
   
   if(i!=size-1)
   
   cur=genNextRow(cur);
   
  }
  
  //Creating upper and left boundary
  
  for(int i=0;i<=2*size;i++)
  
  maze[i][0]=maze[0][i]=maze[i][2*size]=maze[2*size][i]=1;
  
  for(int i=2;i<=2*size;i+=2)
  
  for(int j=2;j<=2*size;j+=2)
  
  maze[i][j]=1;
  
  for(int i=0;i<2*size+1;i++){
   
   System.out.println();
   
   for(int j=0;j<2*size+1;j++)
   
   System.out.print(maze[i][j]+" ");
   
  }
  
 }
 
 static Cel[] end(Cel[] row) {
  
  for(int i = 1; i < row.length; i++) {
   
   if(findPos(row[i-1].set,row[i]) == -1) {
    
    row[i-1].right=false;
    
    row=merge(row,i);
    
   }
   
  }
  
  return row;
  
 }
 
 
 
 static int findPos(List<Cel> set,Cel x){
  
  Cel[] tmpArray = new Cel[set.size()];
  
  tmpArray = set.toArray(tmpArray);
  
  for(int i=0;i<tmpArray.length;i++)
  
  if(tmpArray[i]==x)
  
  return i;
  
  return -1;
  
 }
 
 
 
 static Cel[] genNextRow(Cel[] pre){
  
  for(int i = 0; i < pre.length;i++ ) {
   
   pre[i].right=false;
   
   pre[i].x++;
   
   if(pre[i].down) {
    
    pre[i].set.remove(findPos(pre[i].set, pre[i]));
    
    pre[i].set=null;
    
    pre[i].down=false;
    
   }
   
  }
  
  return pre;
  
 }
 
 
 
 static void printMaze(Cel[] row,int rowPos){
  
  rowPos=2*rowPos+1;
  
  for(int i=0;i<row.length;i++){
   
   if(row[i].right)
   
   maze[rowPos][2*i+2]=1;
   
   if(row[i].down)
   
   maze[rowPos+1][2*i+1]=1;
   
  }
  
 }
 
 
 
}

// driver class to execute the algorithm
public class runMe{
 
 public static void main(String[] args) {
  
  maze t =new maze();
  
  maze.driver();
  
 }
 
}

SOURCE:

http://www.neocomputer.org/projects/eller.html

JAVA program to help jerry find cheese

noreply@blogger.com (Anonymous) — Mon, 04 May 2015 07:46:00 +0000

ALGORITHM:

Jerry is hungry and needs cheese. Bur cheese is in a maze and jerry needs help to find the cheese.
The maze solving is a classic algorithm under backtracking and ai.The problem is to find a path for the rat to food in a maze.
The problem can be solved trying out different paths possible and find the right path,
This logic can be implemented by a simple recursive algorithm. Since the jerryis performed in stack the processes are done in LIFO manner so if we have to print instructions to jerry we will do the process as cheese finds jerry.

Start with the target
If the cell is not legal (if it is out of maze or the cell is a wall) return false
If starting point has reached return true
else make the cell a wall(to avoid coming back to the same path from any other instant) and
Take all the cells in four direction and check whether the path can be reached through any of these cells and print opposite movement if the cell is a part of the path (eg if upper cell is part of path print DOWN)and return true and if not path backtrack and return false.These cells should chosen according to the distance to starting point from the current point.

The above maze is:

1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
1 0 0 1 0
1 1 1 1 0

So the jerry should move down four times and right three times and up two times and right and then up two times.

CODE:

import java.util.Scanner;

public class Maze{


    static Scanner in = new Scanner(System.in);
    static int[][] maze;

    static boolean solveMaze(int x,int y,int tx,int ty,int b,int h){

        if(x>=0 && x<b && y>=0 && y<h && maze[x][y]==1){//Checking if current cell is legal
            maze[x][y]-=1;
            if(x==tx && y==ty)//checking if point has reached
                return true;
            boolean up,down,left,right;
            /*

Calculating horizontal and vertical distances and moving according to it

            int xDiff=tx-x;
            if(xDiff<0)
                xDiff*=-1;
            int yDiff=ty-y;
            if(yDiff<0)
                yDiff*=-1;
            if(xDiff<yDiff){
                if(tx<x){
                    up=solveMaze(x-1,y,tx,ty,b,h);
                    down=solveMaze(x+1,y,tx,ty,b,h);
                }
                else{
                    down=solveMaze(x+1,y,tx,ty,b,h);
                    up=solveMaze(x-1,y,tx,ty,b,h);
                }
                if(ty<y){
                    left=solveMaze(x,y-1,tx,ty,b,h);
                    right=solveMaze(x,y+1,tx,ty,b,h);
                }
                else{
                    right=solveMaze(x,y+1,tx,ty,b,h);
                    left=solveMaze(x,y-1,tx,ty,b,h);
                }
            }
            else{
                if(ty<y){
                    left=solveMaze(x,y-1,tx,ty,b,h);
                    right=solveMaze(x,y+1,tx,ty,b,h);
                }
                else{
                    right=solveMaze(x,y+1,tx,ty,b,h);
                    left=solveMaze(x,y-1,tx,ty,b,h);
                }
                if(tx<x){
                    up=solveMaze(x-1,y,tx,ty,b,h);
                    down=solveMaze(x+1,y,tx,ty,b,h);
                }
                else{
                    down=solveMaze(x+1,y,tx,ty,b,h);
                    up=solveMaze(x-1,y,tx,ty,b,h);
                }
            }

            //print opposite movement if the cell is a part of the path
            if(up||down||left||right){
                if(up)
                    System.out.println("DOWN");
                if(down)
                    System.out.println("UP");
                if(left)
                    System.out.println("RIGHT");
                if(right)
                    System.out.println("LEFT");
                return true;
            }
            maze[x][y]+=1;//backtrack
            return false;
        }
        return false;
    }
    public static void main(String[] args) {
        System.out.println("enter number of rows and columns ");
        System.out.print("Rows: ");
        int b = in.nextInt();
        System.out.print("Columns: ");
        int h = in.nextInt();
        maze=new int[b][h];
        System.out.println("enter maze 1 for path and 0 for wall");
        for(int i=0;i<b;i++)
            for(int j=0;j<h;j++)
                maze[i][j]=in.nextInt();
        System.out.print("Enter Jerry position\nX: ");
        int begx=in.nextInt();
        System.out.print("Y: ");
        int begy=in.nextInt();
        System.out.print("Enter cheese position\nX: ");
        int tarx=in.nextInt();
        System.out.print("Y: ");
        int tary=in.nextInt();
        if(!solveMaze(tarx,tary,begx,begy,b,h))
        System.out.println("no path");
    }
}

OUTPUT:

enter number of rows and columns
Rows: 5
Columns: 5
enter maze 1 for path and 0 for wall
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
1 0 0 1 0
1 1 1 1 0
Enter Jerry position
X: 0
Y: 0
Enter cheese position
X: 0
Y: 4

DOWN
DOWN
DOWN
DOWN
RIGHT
RIGHT
RIGHT
UP
UP
RIGHT
UP
UP

JAVA program to print all permutations of a string

noreply@blogger.com (Anonymous) — Tue, 28 Apr 2015 04:23:00 +0000

ALGORITHM:

The permutation of a string is the rearrangement of the string in different orders to form different strings of the same length. A string of length n can have n! permutations.

Source: Mathworld

We will start with each letter of the string and then we found all the possible combinations for the string beginning with that letter. And once we picked a letter in the 2nd position, we then found all the possible combinations that begin with that 2 letter sequence before we changed any of the letters in the first 2 positions. So, basically what we did was choose a letter and then peformed the permutation process starting at the next position to the right before we come back and change the character on the left.

CODE:

import java.util.Scanner;

public class permutations{

    static char[] swap(char[] a,int i,int j){
        char tmp =a[i];
        a[i]=a[j];
        a[j]=tmp;
        return a;
    }

    static void printArray(char[] a){
        for (int i=0;i<a.length;i++)
            System.out.print(a[i]);
        System.out.println();
    }

    static void permute(char[] a,int index){
        if(index==a.length){
            printArray(a);
            return;
        }
        for(int i=index;i<a.length;i++){
            a=swap(a,i,index);
            permute(a,index+1);
            a=swap(a,i,index);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("Enter the string: ");
        permute(in.next().toCharArray(),0);
    }
}

OUTPUT:

Enter the string: abc
abc
acb
bac
bca
cba
cab

JAVA program to print all combinations(NOT PERMUTATIONS) of a string

noreply@blogger.com (Anonymous) — Mon, 27 Apr 2015 08:21:00 +0000

ALGORITHM:

The problem is to find all combination of letters in a string ,the question should not be mistaken with permutation of string.To find all combinations of a string we follow a simple method: take each element and and group it with rest of the elements and do the same for thus formed new groups.

A diagramatic representation for the string ABC is:

So this logic can be implemented using a recursive algorithm :

Take each group(each elements in beginning) and form new groups for each group by combining it with the rest of elements and repeat this procedure for each newly formed groups until the group size becomes equal to the string size.

CODE:

import java.util.Scanner;

public class comb{

    static void printArray(char[] a,int len){
        for (int i=0;i<=len;i++)
            System.out.print(a[i]);
        System.out.println();
    }

    static void printCombination(char[] a,char[] b,int aBeg,int bEnd){
        for(int i=aBeg;i<a.length;i++){
            b[bEnd+1]=a[i];
            printArray(b,bEnd+1);
            if(i<a.length-1)
                printCombination(a,b,i+1,bEnd+1);
        }
    }

    public static void main(String[] args) {
        System.out.print("Enter string: ");
        char[] a;
        Scanner in = new Scanner(System.in);
        a=in.next().toCharArray();
        char[] b = new char[a.length];
        printCombination(a,b,0,-1);
    }
}

OUTPUT:

Enter string: abc
a
ab
abc
ac
b
bc
c

JAVA program to find all numbers whose sum of digits is equal to an input number

noreply@blogger.com (Anonymous) — Sun, 26 Apr 2015 11:44:00 +0000

ALGORITHM:

The problem is to input a number and find all numbers whose digits sum is equal to the input number.

i.e. if the input number is 5 then program should print numbers 5 14 23 32 41.

The problem can be solved by doing a recursive algorithm given below:

Start with first digit 1 to 9
Check whether the number digit's sum has exceeded the target or has reached the target; if it has reached target then print the number; if so return from the function.
If the digit's sum is less than target then try adding digits 1 to 9 to the LSB of the number and recurse the function(from step 2) for each such made new numbers.

The program of algorithm is given below since java has a stack limit of about 1k bytes the program won't work for large numbers :P.

CODE:

import java.util.Scanner;

public class digitSum{

    static boolean isInArray(int[] a,int ele){
        for(int i=0;i<a.length;i++)
            if(a[i]==ele)
                return false;
        return true;
    }

    static int findSum(int[] ar,int end){
        int sum=0;
        for(int i=0;i<=end;i++)
            sum+=ar[i];
        return sum;
    }

    static void printNum(int[] ar,int index,int num){

        int sum = findSum(ar,index);
        int diff = num-sum;
        if(diff<0)
            return;
        if(diff==0){
            for (int i=0;i<=index;i++)
                System.out.print(ar[i]);
            System.out.println();
            return;
        }
        for(int i=1;i<10;i++){
            if(isInArray(ar,i)){
                ar[index+1]=i;
                printNum(ar,index+1,num);
            }
        }

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("\nEnter the number: ");
        int num=in.nextInt();
        int[] ar = new int[9];
        for (int i=1;i<=9;i++ ) {
            ar[0]=i;
            printNum(ar,0,num);
        }
    }
}

OUTPUT:

Enter the number: 8
125
134
143
152
17
215
251
26
314
341
35
413
431
512
521
53
62
71
8

JAVA program to perform iterative preorder traversal

noreply@blogger.com (Anonymous) — Thu, 23 Apr 2015 14:43:00 +0000

CODE:

import java.util.Scanner;
import java.util.Stack;

public class iterPre{

    static Scanner in = new Scanner(System.in);

        static node inputTree(){
        node temp=new node();
        System.out.print("Enter the value: ");
        temp.data=in.nextInt();
        System.out.print("Enter y if the node "+temp.data+" has left subtree: ");
        if(in.next().charAt(0)=='y')
            temp.left=inputTree();
        else
            temp.left=null;
        System.out.print("Enter y if the node "+temp.data+" has right subtree: ");
        if(in.next().charAt(0)=='y')
            temp.right=inputTree();
        else
            temp.right=null;
        return temp;
    }

    static void iterPreorder(node root){
        if(root == null)
            return;
        node tmp = new node();
        Stack<node> s = new Stack<node>();
        s.push(root);
        while (s.isEmpty()==false) {
            tmp = s.pop();
            System.out.print("\t"+tmp.data);
            if(tmp.right != null)
                s.push(tmp.right);
            if(tmp.left != null)
                s.push(tmp.left);
        }
    }

    public static void main(String[] args) {
        node root = new node();
        root = inputTree();
        iterPreorder(root);
    }

}

JAVA program to traverse inorder without recursion

noreply@blogger.com (Anonymous) — Fri, 17 Apr 2015 05:58:00 +0000

CODE:

import java.util.Scanner;
import java.util.Stack;

public class inorderStack{

    static Scanner in = new Scanner(System.in);

    static node inputTree(){
        node temp=new node();
        System.out.print("Enter the value: ");
        temp.data=in.nextInt();
        System.out.print("Enter y if the node "+temp.data+" has left subtree: ");
        if(in.next().charAt(0)=='y')
            temp.left=inputTree();
        else
            temp.left=null;
        System.out.print("Enter y if the node "+temp.data+" has right subtree: ");
        if(in.next().charAt(0)=='y')
            temp.right=inputTree();
        else
            temp.right=null;
        return temp;
    }

    static void inorder(node tree){
        if(tree == null)
            return;
        Stack<node> s = new Stack<node>();
        while((s.isEmpty() == false)||(tree != null)){
            if(tree!=null){
                s.push(tree);
                tree = tree.left;
            }
            else{
                tree = s.pop();
                System.out.print(tree.data+"\t");
                tree = tree.right;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("Enter the tree: ");
        node tree = new node();
        tree = inputTree();
        System.out.println("Inorder traversal ");
        inorder(tree);
    }

}

JAVA program to find sibling of parent of a given node

noreply@blogger.com (Anonymous) — Fri, 17 Apr 2015 05:01:00 +0000

CODE:

import java.util.Scanner;

public class parentSibling{

    static Scanner in = new Scanner(System.in);

    static node inputTree(){
        node temp=new node();
        System.out.print("Enter the value: ");
        temp.data=in.nextInt();
        System.out.print("Enter y if the node "+temp.data+" has left subtree: ");
        if(in.next().charAt(0)=='y')
            temp.left=inputTree();
        else
            temp.left=null;
        System.out.print("Enter y if the node "+temp.data+" has right subtree: ");
        if(in.next().charAt(0)=='y')
            temp.right=inputTree();
        else
            temp.right=null;
        return temp;
    }

    static void inorder(node tree){
        if(tree==null)
            return;
        inorder(tree.left);
        System.out.print(tree.data+"\t");
        inorder(tree.right);
    }

    static void printSibling(node tree,node par,node parofpar,int X){
        if(tree == null)
            return;
        if(tree.data==X){
            if((par != null)&&(parofpar != null)&&(parofpar.left != null)&&(parofpar.right != null)){
                if(parofpar.left == par)
                    System.out.println("Sibling "+parofpar.right.data);
                if(parofpar.right == par)
                    System.out.println("Sibling "+parofpar.left.data);
            }
            else
                System.out.println("No Sibling");
            return;
        }
        printSibling(tree.left,tree,par,X);
        printSibling(tree.right,tree,par,X);
    }

    public static void main(String[] args) {
        System.out.println("Enter the tree: ");
        node tree = new node();
        tree = inputTree();
        System.out.println("Inorder traversal ");
        inorder(tree);
        System.out.print("\nEnter node: ");
        printSibling(tree,null,null,in.nextInt());
    }

}

JAVA program to build a tree from inorder and postorder traversals

noreply@blogger.com (Anonymous) — Thu, 16 Apr 2015 01:52:00 +0000

CODE:

import java.util.Scanner;

public class InPosttoTree{

    static Scanner in = new Scanner(System.in);
    static int postIndex;

    static void inorder(node tree){
        if(tree==null)
            return;
        inorder(tree.left);
        System.out.print(tree.data+"\t");
        inorder(tree.right);
    }

    static void preorder(node tree){
        if(tree==null)
            return;
        System.out.print(tree.data+"\t");
        preorder(tree.left);
        preorder(tree.right);
    }

    static void postorder(node tree){
        if(tree==null)
            return;
        postorder(tree.left);
        postorder(tree.right);
        System.out.print(tree.data+"\t");
    }

    static node cnvrt(int[] inorder,int instart,int inend,int[] postorder){
            if((instart>inend))
                return null;
            node temp = new node();
            temp.data = postorder[postIndex--];
            if(instart==inend){
                temp.left=temp.right=null;
                return temp;
            }
            int i;
            for (i=0;(i<inorder.length)&&(inorder[i]!=temp.data);i++);
            temp.right = cnvrt(inorder,i+1,inend,postorder);
            temp.left = cnvrt(inorder,instart,i-1,postorder);
            return temp;
    }

    public static void main(String[] args) {
        int len;
        System.out.print("\nEnter length: ");
        len = in.nextInt();
        int[] iar = new int[len];
        int[] par = new int[len];
        int i;
        System.out.println("Enter inorder traversal");
        for(i=0;i<len;i++)
            iar[i] = in.nextInt();
        System.out.println("Enter postorder traversal");
        for(i=0;i<len;i++)
            par[i] = in.nextInt();
        node tree = new node();
        postIndex=len-1;
        tree = cnvrt(iar,0,len-1,par);
        System.out.println("Inorder traversal of the tree is:");
        inorder(tree);
        System.out.println("\nPreorder traversal of the tree is:");
        preorder(tree);
        System.out.println("\nPostorder traversal of the tree is");
        postorder(tree);
    }
}

JAVA program to build a tree from inorder and preorder traversals

noreply@blogger.com (Anonymous) — Thu, 16 Apr 2015 01:48:00 +0000

CODE:

import java.util.Scanner;

public class InPreToTree{

    static Scanner in = new Scanner(System.in);
    static int preIndex;

    static void inorder(node tree){
        if(tree==null)
            return;
        inorder(tree.left);
        System.out.print(tree.data+"\t");
        inorder(tree.right);
    }

    static void preorder(node tree){
        if(tree==null)
            return;
        System.out.print(tree.data+"\t");
        preorder(tree.left);
        preorder(tree.right);
    }

    static void postorder(node tree){
        if(tree==null)
            return;
        postorder(tree.left);
        postorder(tree.right);
        System.out.print(tree.data+"\t");
    }

    static node cnvrt(int[] inorder,int instart,int inend,int[] preorder){
            if((instart>inend))
                return null;
            node temp = new node();
            temp.data = preorder[preIndex++];
            if(instart==inend){
                temp.left=temp.right=null;
                return temp;
            }
            int i;
            for (i=0;(i<inorder.length)&&(inorder[i]!=temp.data);i++);
            temp.left = cnvrt(inorder,instart,i-1,preorder);
            temp.right = cnvrt(inorder,i+1,inend,preorder);
            return temp;
    }

    public static void main(String[] args) {
        int len;
        System.out.print("\nEnter length: ");
        len = in.nextInt();
        int[] iar = new int[len];
        int[] par = new int[len];
        int i;
        System.out.println("Enter inorder traversal");
        for(i=0;i<len;i++)
            iar[i] = in.nextInt();
        System.out.println("Enter preorder traversal");
        for(i=0;i<len;i++)
            par[i] = in.nextInt();
        node tree = new node();
        preIndex=0;
        tree = cnvrt(iar,0,len-1,par);
        System.out.println("Inorder traversal of the tree is:");
        inorder(tree);
        System.out.println("\nPreorder traversal of the tree is:");
        preorder(tree);
        System.out.println("\nPostorder traversal of the tree is");
        postorder(tree);
    }
}

JAVA program to find height of a node in a binary tree

noreply@blogger.com (Anonymous) — Wed, 15 Apr 2015 16:13:00 +0000

CODE:

import java.util.Scanner;

public class nodeHeight{
    static int height,nod;
    static void traverse(node tree,int currHeight){
        if(tree==null)
            return;
        if(tree.data==nod){
            height=currHeight+1;
            return;
        }
        if(height == -1){
            traverse(tree.left,currHeight+1);
            traverse(tree.right,currHeight+1);
        }
    }

    static Scanner in = new Scanner(System.in);

    static node inputTree(){
        node temp=new node();
        System.out.print("Enter the value: ");
        temp.data=in.nextInt();
        System.out.print("Enter y if the node "+temp.data+" has left subtree: ");
        if(in.next().charAt(0)=='y')
            temp.left=inputTree();
        else
            temp.left=null;
        System.out.print("Enter y if the node "+temp.data+" has right subtree: ");
        if(in.next().charAt(0)=='y')
            temp.right=inputTree();
        else
            temp.right=null;
        return temp;
    }

    public static void main(String[] args) {
        node tree = new node();
        System.out.println("Enter tree:");
        tree = inputTree();
        height = -1;
        System.out.print("Enter node:");
        nod=in.nextInt();
        traverse(tree,0);
        if(height==-1)
            System.out.println("Node not found");
        else
            System.out.print("Node is at height "+height);
    }
}

OUTPUT:

Enter tree:
Enter the value: 5
Enter y if the node 5 has left subtree: y
Enter the value: 2
Enter y if the node 2 has left subtree: y
Enter the value: 1
Enter y if the node 1 has left subtree: n
Enter y if the node 1 has right subtree: n
Enter y if the node 2 has right subtree: y
Enter the value: 3
Enter y if the node 3 has left subtree: n
Enter y if the node 3 has right subtree: y
Enter the value: 4
Enter y if the node 4 has left subtree: n
Enter y if the node 4 has right subtree: n
Enter y if the node 5 has right subtree: y
Enter the value: 6
Enter y if the node 6 has left subtree: n
Enter y if the node 6 has right subtree: n
Enter node:1
Node is at height 3

NOT SURE WITH THE CODE PLS INFRM IF THERE ARE ANY TESTCASES IN WHICH THE CODE FAILS

JAVA program to swap head and tail of a linked list

noreply@blogger.com (Anonymous) — Wed, 15 Apr 2015 15:50:00 +0000

CODE:

import java.util.Scanner;

public class swapHeadTail{

    static llistNode insert(llistNode H,int data){
        llistNode tmp = new llistNode();
        tmp.data=data;
        tmp.next=null;
        if(H==null)
            return tmp;
        llistNode curr = new llistNode();
        curr = H;
        while(curr.next != null)
            curr = curr.next;
        curr.next = tmp;
        return H;
    }

    public static void main(String[] args) {
        llistNode H = new llistNode();
        Scanner in = new Scanner(System.in);
        llistNode tmp =new llistNode();

        H=null;
        do{
            System.out.print("Enter data:");
            H=insert(H,in.nextInt());
            System.out.print("Enter 1 to continue: ");
        }while (in.nextInt()==1);

        tmp = H;
        while(tmp != null){
            System.out.print(tmp.data+"\t");
            tmp = tmp.next;
        }

System.out.println();

        llistNode head = new llistNode();
        llistNode headNext = new llistNode();
        llistNode tailPrev = new llistNode();
        llistNode tail = new llistNode();

        head = H;
        headNext = H.next;
        tailPrev = H;
        while(tailPrev.next.next != null)
            tailPrev=tailPrev.next;
        tail = tailPrev.next;
        if ((tailPrev == head)&&(headNext == tail)){
            head.next = null;
            tail.next = head;
        }
        else{
            tmp = head;
            tmp.next = null;
            tailPrev.next = tmp;
            tail.next=headNext;
        }
        H=tail;
        tmp = H;
        while(tmp != null){
            System.out.print(tmp.data+"\t");
            tmp = tmp.next;
        }

    }
}

OUTPUT:

Enter data:1
Enter 1 to continue: 1
Enter data:2
Enter 1 to continue: 0
1 2
2 1

Program to input a linked list and output the sorted linked list

noreply@blogger.com (AppLord) — Tue, 14 Apr 2015 19:19:00 +0000

import java.util.*;

class ll{
static class node{
int data;
node next;
}
public static node insert(node h,int x){
node current =new node();
node temp = new node();
temp.data=x;
if(h==null)
{
temp.next=null;
h=temp;
}
else {
current = h;
while(current.next!=null)
current = current.next;
temp.next=null;
current.next=temp;
}
return h;
}
public static void display(node h){
node current =new node();
current = h;
while (current!=null)
{
if(current.next!=null)
System.out.print(current.data + "->");
else
System.out.print(current.data);
current=current.next;
}
}
public static node sort(node h){
node current =new node();
node temp = new node();
node navigate = new node();
current=h;
if(h==null)
return null;
else
{
while (current!=null){
navigate=current.next;
while(navigate!=null){
if(navigate.data<current.data)
{
temp.data=current.data;
current.data=navigate.data;
navigate.data=temp.data;
}
navigate=navigate.next;
}
current=current.next;
}
}
return h;
}
public static void main(String args[])
{
int k=0;
System.out.println("Program to input a linked list and output the sorted linked list.Print the output at each step");
node h = new node();
h=null;
while(k==0){
System.out.println("Add an element:(Enter 1 to add an element or 0 to exit)");
Scanner in = new Scanner(System.in);
int u =in.nextInt();
if(u==1)
{
System.out.println("Enter the data to insert:");
int data = in.nextInt();
h = insert(h,data);
display(h);
h=sort(h);
System.out.println("\n");
display(h);
System.out.println("\n");
}
else
k=1;
}
}
}

JAVA program to convert an array to binary tree

noreply@blogger.com (Anonymous) — Tue, 14 Apr 2015 07:25:00 +0000

CODE:

import java.util.Scanner;

public class arrayToBinaryTree{

    static Scanner in = new Scanner(System.in);

    static void inorder(node tree){
        if(tree==null)
            return;
        inorder(tree.left);
        System.out.print(tree.data+"\t");
        inorder(tree.right);
    }

    static void preorder(node tree){
        if(tree==null)
            return;
        System.out.print(tree.data+"\t");
        preorder(tree.left);
        preorder(tree.right);
    }

    static void postorder(node tree){
        if(tree==null)
            return;
        postorder(tree.left);
        postorder(tree.right);
        System.out.print(tree.data+"\t");
    }

    static node cnvrt(int[] ar,int pos){
        if((pos>ar.length-1)||(ar[pos]==-1))
            return null;
        node tmp = new node();
        tmp.data = ar[pos];
        tmp.left = cnvrt(ar,2*pos+1);
        tmp.right = cnvrt(ar,2*pos+2);
        return tmp;
    }

    public static void main(String[] args) {
        int len;
        System.out.print("\nEnter length: ");
        len = in.nextInt();
        int[] ar = new int[len];
        int i;
        for(i=0;i<len;i++)
            ar[i] = in.nextInt();
        node tree = new node();
        tree = cnvrt(ar,0);
        System.out.println("Inorder traversal of the tree is:");
        inorder(tree);
        System.out.println("\nPreorder traversal of the tree is:");
        preorder(tree);
        System.out.println("\nPostorder traversal of the tree is");
        postorder(tree);
    }
}

OUTPUT:

Enter length: 7
2 1 4 -1 -1 3 5
Inorder traversal of the tree is:
1    2    3    4    5
Preorder traversal of the tree is:
2    1    4    3    5
Postorder traversal of the tree is
1    3    5    4    2

JAVA program to convert a sorted array to BST

noreply@blogger.com (Anonymous) — Tue, 14 Apr 2015 07:16:00 +0000

CODE:

import java.util.Scanner;

public class sortedArraytoBST{

    static Scanner in = new Scanner(System.in);

    static void inorder(node tree){
        if(tree==null)
            return;
        inorder(tree.left);
        System.out.print(tree.data+"\t");
        inorder(tree.right);
    }

    static void preorder(node tree){
        if(tree==null)
            return;
        System.out.print(tree.data+"\t");
        preorder(tree.left);
        preorder(tree.right);
    }

    static void postorder(node tree){
        if(tree==null)
            return;
        postorder(tree.left);
        postorder(tree.right);
        System.out.print(tree.data+"\t");
    }

    static node convrt(int[] ar,int start,int end){
        if(start>end)
            return null;
        int mid = (start+end)/2;
        node tmp = new node();
        tmp.data = ar[mid];
        tmp.left = convrt(ar,start,mid-1);
        tmp.right = convrt(ar,mid+1,end);
        return tmp;
    }

    public static void main(String[] args) {
        int len;
        System.out.print("\nEnter length: ");
        len = in.nextInt();
        int[] ar = new int[len];
        int i;
        for(i=0;i<len;i++)
            ar[i] = in.nextInt();
        node tree = new node();
        tree = convrt(ar,0,len-1);
        System.out.println("Inorder traversal of the tree is:");
        inorder(tree);
        System.out.println("\nPreorder traversal of the tree is:");
        preorder(tree);
        System.out.println("\nPostorder traversal of the tree is");
        postorder(tree);
    }
}

OUTPUT:

Enter length: 5
1 2 3 4 5
Inorder traversal of the tree is:
1    2    3    4    5
Preorder traversal of the tree is:
3    1    2    4    5
Postorder traversal of the tree is
2    1    5    4    3

JAVA program to find the lowest common ancestor of a binary tree

noreply@blogger.com (Anonymous) — Tue, 14 Apr 2015 06:03:00 +0000

CODE:

import java.util.Scanner;

public class lowestcommonAnc{
    static Scanner in =new Scanner(System.in);

    static node inputTree(){
        node temp=new node();
        System.out.print("Enter the value: ");
        temp.data=in.nextInt();
        System.out.print("Enter y if the node "+temp.data+" has left subtree: ");
        if(in.next().charAt(0)=='y')
            temp.left=inputTree();
        else
            temp.left=null;
        System.out.print("Enter y if the node "+temp.data+" has right subtree: ");
        if(in.next().charAt(0)=='y')
            temp.right=inputTree();
        else
            temp.right=null;
        return temp;
    }

    static void inorder(node tree){
        if(tree==null)
            return;
        inorder(tree.left);
        System.out.print(tree.data+"\t");
        inorder(tree.right);
    }

    static node lca(node tree,int n1,int n2){
        if(tree == null)
            return tree;
        if((tree.data>n1)&&(tree.data>n2))
            return lca(tree.left,n1,n2);
        if((tree.data<n1)&&(tree.data<n2))
            return lca(tree.right,n1,n2);
        return tree;
    }

    public static void main(String[] args) {
        node tree=new node();
        System.out.print("Enter y if tree is null: ");
        if(in.next().charAt(0)=='y')
            tree=null;
        else
            tree=inputTree();
        if(tree != null){
            System.out.print("Inorder traversal of the tree is:\n");
            inorder(tree);
            System.out.print("\nEnter the node 1:");
            int n1 = in.nextInt();
            System.out.print("Enter the node 2:");
            int n2 = in.nextInt();
            System.out.print("Lowest commom ancestor is:"+lca(tree,n1,n2).data);
        }
    }
}

OUTPUT:

Enter y if tree is null: n
Enter the value: 8
Enter y if the node 8 has left subtree: y
Enter the value: 3
Enter y if the node 3 has left subtree: y
Enter the value: 1
Enter y if the node 1 has left subtree: n
Enter y if the node 1 has right subtree: n
Enter y if the node 3 has right subtree: y
Enter the value: 6
Enter y if the node 6 has left subtree: y
Enter the value: 4
Enter y if the node 4 has left subtree: n
Enter y if the node 4 has right subtree: n
Enter y if the node 6 has right subtree: y
Enter the value: 7
Enter y if the node 7 has left subtree: n
Enter y if the node 7 has right subtree: n
Enter y if the node 8 has right subtree: y
Enter the value: 10
Enter y if the node 10 has left subtree: n
Enter y if the node 10 has right subtree: y
Enter the value: 14
Enter y if the node 14 has left subtree: y
Enter the value: 13
Enter y if the node 13 has left subtree: n
Enter y if the node 13 has right subtree: n
Enter y if the node 14 has right subtree: n
Inorder traversal of the tree is:
1 3 4 6 7 8 10 13 14
Enter the node 1:1
Enter the node 2:7
Lowest commom ancestor is:3

JAVA program to do preorder,inorder,postorder traversals in a binary tree

noreply@blogger.com (Anonymous) — Mon, 13 Apr 2015 13:21:00 +0000

ALGORITHM:

We have 3 types of tree traversals

Preorder traversal
Inorder traversal
Postorder traversal

In preorder traversal a node is visited then its left and right subtree is visite.
In inorder traversal a node is visited after visiting its left subtree then it passes to the right subtree
In postorder traversal a node is visited after its left and right subtree is visited or either of it or both are null.

Algorithm in detail is in this link.

CODE:

//utility class for node

public class node{
    public int data;
    public node left,right;
    public node(){
       data=0;
       left=right=null;
    }
}

//class to implement the algorithm
import java.util.Scanner;

public class treeTraversals {

    static Scanner in = new Scanner(System.in);

    static node inputTree(){
        node temp=new node();
        System.out.print("Enter the value: ");
        temp.data=in.nextInt();
        System.out.print("Enter y if the node "+temp.data+" has left subtree: ");
        if(in.next().charAt(0)=='y')
            temp.left=inputTree();
        else
            temp.left=null;
        System.out.print("Enter y if the node "+temp.data+" has right subtree: ");
        if(in.next().charAt(0)=='y')
            temp.right=inputTree();
        else
            temp.right=null;
        return temp;
    }
    static void inorder(node tree){
        if(tree==null)
            return;
        inorder(tree.left);
        System.out.print(tree.data+"\t");
        inorder(tree.right);
    }

    static void preorder(node tree){
        if(tree==null)
            return;
        System.out.print(tree.data+"\t");
        preorder(tree.left);
        preorder(tree.right);
    }

    static void postorder(node tree){
        if(tree==null)
            return;
        postorder(tree.left);
        postorder(tree.right);
        System.out.print(tree.data+"\t");
    }

    public static void main(String[] args) {
        System.out.println("Enter the tree: ");
        node tree = new node();
        tree = inputTree();
        System.out.println("Inorder traversal ");
        inorder(tree);
        System.out.println("\nPreorder traversal ");
        preorder(tree);
        System.out.println("\nPostorder traversal ");
        postorder(tree);
    }
}

OUTPUT:

Enter the tree:
Enter the value: 2
Enter y if the node 2 has left subtree: y
Enter the value: 7
Enter y if the node 7 has left subtree: y
Enter the value: 2
Enter y if the node 2 has left subtree: n
Enter y if the node 2 has right subtree: n
Enter y if the node 7 has right subtree: y
Enter the value: 6
Enter y if the node 6 has left subtree: y
Enter the value: 5
Enter y if the node 5 has left subtree: n
Enter y if the node 5 has right subtree: n
Enter y if the node 6 has right subtree: y
Enter the value: 11
Enter y if the node 11 has left subtree: n
Enter y if the node 11 has right subtree: n
Enter y if the node 2 has right subtree: y
Enter the value: 5
Enter y if the node 5 has left subtree: n
Enter y if the node 5 has right subtree: y
Enter the value: 9
Enter y if the node 9 has left subtree: y
Enter the value: 4
Enter y if the node 4 has left subtree: n
Enter y if the node 4 has right subtree: n
Enter y if the node 9 has right subtree: n
Inorder traversal
2   7   5   6   11   2   5   4   9
Preorder traversal
2   7   2   6   5   11   5   9   4
Postorder traversal
2   5   11   6   7   4   9   5   2

JAVA program to print ancestors of a node in a BST

noreply@blogger.com (Anonymous) — Mon, 13 Apr 2015 13:03:00 +0000

ALGORITHM:

To print ancestors of a node in a BST , we just add a print function to the searching function of a BST before the recursion.

Steps in a search function of BST:

if current node is the required node print the node
if current node is greater than required node goto step 1 for left subtree
if current node is lesser than required node goto step 1 for right subtree

CODE:

//utility class for node

public class node{
    public int data;
    public node left,right;
    public node(){
       data=0;
       left=right=null;
    }
}

//class to implement the algorithm
import java.util.Scanner;

public class ancestorsNode {

    static Scanner in =new Scanner(System.in);

    static node inputTree(){
        node temp=new node();
        System.out.print("Enter the value: ");
        temp.data=in.nextInt();
        System.out.print("Enter y if the node "+temp.data+" has left subtree: ");
        if(in.next().charAt(0)=='y')
            temp.left=inputTree();
        else
            temp.left=null;
        System.out.print("Enter y if the node "+temp.data+" has right subtree: ");
        if(in.next().charAt(0)=='y')
            temp.right=inputTree();
        else
            temp.right=null;
        return temp;
    }

    static void inorder(node tree){
        if(tree==null)
            return;
        inorder(tree.left);
        System.out.print(tree.data+"\t");
        inorder(tree.right);
    }

    public static void printAnc(node tree,int nod){

        if(nod==tree.data){
            System.out.println(nod);
            return;
        }
        System.out.print(tree.data+"---");
        if(nod<tree.data)
            printAnc(tree.left,nod);

        else
            printAnc(tree.right,nod);
    }

    public static void main(String[] args) {
        node tree=new node();
        System.out.print("Enter y if tree is null: ");
        if(in.next().charAt(0)=='y')
            tree=null;
        else
            tree=inputTree(tree);
        System.out.print("Inorder traversal of the tree is:\n");
        inorder(tree);
        System.out.print("\nEnter the node:");
        int nd = in.nextInt();
        printAnc(tree,nd);
        in.close();
    }
}

OUTPUT:

Enter y if tree is null: n
Enter the value: 5
Enter y if the node 5 has left subtree: y
Enter the value: 3
Enter y if the node 3 has left subtree: y
Enter the value: 2
Enter y if the node 2 has left subtree: n
Enter y if the node 2 has right subtree: n
Enter y if the node 3 has right subtree: y
Enter the value: 4
Enter y if the node 4 has left subtree: n
Enter y if the node 4 has right subtree: n
Enter y if the node 5 has right subtree: y
Enter the value: 7
Enter y if the node 7 has left subtree: y
Enter the value: 6
Enter y if the node 6 has left subtree: n
Enter y if the node 6 has right subtree: n
Enter y if the node 7 has right subtree: y
Enter the value: 8
Enter y if the node 8 has left subtree: n
Enter y if the node 8 has right subtree: n
Inorder traversal of the tree is:
2 3 4 5 6 7 8

Enter the node:8
5---7---8

JAVA program to check whether a binary tree is an BST or not

noreply@blogger.com (Anonymous) — Sun, 12 Apr 2015 14:30:00 +0000

ALGORITHM:

A binary search tree (BST) is a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right subtree.

So to check whether a binary tree is a binary search tree or not we just use a recursive function which passes the left and right subtrees and lower limit and upper limit of the value which the current node can have .

start with the root node with limits positive infinity and negative infinity
return true if reached the leaf
if the current node is legal then recurse the function by passing the left subtree and right subtree with limits passed lower limit argument and current node-1 as lower limit and upper limit for the left subtree and current node+1 and passed upper limit argument as lower limit and upper limit for right subtree.
return false if current node is illegal

CODE:

//utility class for node

public class node{
    public int data;
    public node left,right;
    public node(){
       data=0;
       left=right=null;
    }
}

//class to implement the algorithm

import java.util.Scanner;

class isBST{
    static Scanner in = new Scanner(System.in);
    static boolean isBSTree(node tree,int min,int max){
        if((tree==null)||((tree.left==null)&&(tree.right==null)))
            return true;
        if((tree.right==null)&&(tree.left.data<=max))
            return isBSTree(tree.left,min,tree.left.data-1);
        if((tree.left==null)&&(tree.right.data>=min))
            return isBSTree(tree.right,tree.right.data+1,max);
        if((tree.left.data<=max)&&(tree.right.data>=min))
            return isBSTree(tree.left,min,tree.left.data-1)&&isBSTree(tree.right,tree.right.data+1,max);
        return false;
    }

    static node inputTree(){
        node temp=new node();
        System.out.print("Enter the value: ");
        temp.data=in.nextInt();
        System.out.print("Enter y if the node "+temp.data+" has left subtree: ");
        if(in.next().charAt(0)=='y')
            temp.left=inputTree();
        else
            temp.left=null;
        System.out.print("Enter y if the node "+temp.data+" has right subtree: ");
        if(in.next().charAt(0)=='y')
            temp.right=inputTree();
        else
            temp.right=null;
        return temp;
    }

    static void inorder(node tree){
        if(tree==null)
            return;
        inorder(tree.left);
        System.out.print(tree.data+"\t");
        inorder(tree.right);
    }

    public static void main(String[] args) {
        node tree=new node();
        System.out.print("Enter y if tree is null: ");
        if(in.next().charAt(0)=='y')
            tree=null;
        else
            tree=inputTree();
        System.out.print("Inorder traversal of the tree is:\n");
        inorder(tree);
        if (isBSTree(tree,Integer.MIN_VALUE,Integer.MAX_VALUE))
            System.out.println("\nThe tree is BST....");
        else
            System.out.println("\nThe tree is not BST....");
    }
}

JAVA program to solve N Queens problem

noreply@blogger.com (Anonymous) — Sun, 05 Apr 2015 17:43:00 +0000

ALGORITHM:

The N Queens problem is a classic problem which falls under various categories of algorithm design such as backtracking, brute force searching etc.

For further research on this problem use these links:

Wikipedia

http://www.math.utah.edu/~alfeld/queens/queens.html

http://mathworld.wolfram.com/QueensProblem.html

Okay, now let's comeback to the problem, N queens problem is a classic problem in which we have arrange N queens in a chessboard of dimension N*N, such that no queens should attack each other.

A perfect solution to this problem have been a headache for mathematicians and programmers around the globe. A simple solution though not so ideal solution is posted here.

The problem is solved by a recursive backtracking algorithm the queens are placed in different optimal positions and checked whether it leads to the solution. if not the current position is backtracked and next possible position is checked.
We start with the leftmost column and we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes then we backtrack and return false.

Start with first column
If all queens are placed return true
For the column passed to the function check every row position whether the queen can be placed safely(this is checked using a utility function named isSafe) if so the row is marked as a part of solution and recurse the function for next column. return true if it leads to solution otherwise backtrack.
If all rows have been tried return false which triggers backtracking

CODE:

import java.util.Scanner;

class nQueens {
    static int[][] board;
    static int size;
    static boolean solveProblem(int col){
        if (col>size-1)
            return true;
        for (int i=0;i<size;i++){
            if(isSafe(i,col)){
                board[i][col]=1;
                if(solveProblem(col+1))
                    return true;
                board[i][col]=0;
            }
        }
        return false;
    }

    static boolean isSafe(int row,int col){
        int i,j;
        for(i=0;i<col;i++)
            if (board[row][i]==1)
                return false;
        for(i=row,j=col;(i>=0)&&(j>=0);i--,j--)
            if (board[i][j]==1)
                return false;
        for(i=row,j=col;(j>=0)&&(i<size);i++,j--)
            if (board[i][j]==1)
                return false;
        return true;
    }

    static void printBoard(){
        for (int i=0;i<size;i++) {
            System.out.print("\n");
            for (int j=0;j<size;j++) {
                System.out.print(board[i][j]+"\t");
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("Enter n: ");
        size = in.nextInt();
        board = new int[size][size];
        int i,j;
        for(i=0;i<size;i++)
            for(j=0;j<size;j++)
                board[i][j]=0;
        if (solveProblem(0)) {
            printBoard();
        }
        else {
            System.out.println("No soln...");
        }
    }
}

JAVA program to print IP address

noreply@blogger.com (Anonymous) — Sat, 04 Apr 2015 11:35:00 +0000

import java.net.InetAddress;

class IP{
    public static void main(String[] args) throws Exception {
        System.out.print("IP address:"+InetAddress.getLocalHost());
    }
}

JAVA program to find the maximum number that can be made from an integer array

noreply@blogger.com (Anonymous) — Sat, 04 Apr 2015 09:11:00 +0000

ALGORITHM:

This problem can be simply solved by changing the comparison criteria of any sorting algorithms.

Comparison should be changed as explained

if the two numbers to be compared are a & b then two numbers should be made tempA and tempB such that:
tempA = a*10^(number of digits in b)+b
tempB = b*10^(number of digits in a)+a
if tempA>tempB then a is larger than b and vice versa

Code of the above logic implemented with bubble sort is given below:

CODE:

import java.util.Scanner;

class maxNo{

    static int size(int a){                //simple utility function count no of digits
        int count=0;
        do{
            count++;
            a/=10;
        }while(a!=0);
        return count;
    }
//utility function to implement modified comparison criteria of the sort
    static int[] compare(int[] a,int i,int j){
        double t1,t2;
        int tmp;
        t1=a[i]*Math.pow(10,size(a[j]))+a[j];
        t2=a[j]*Math.pow(10,size(a[i]))+a[i];
        if(t1<t2){
            tmp=a[i];                //swapping ith and jth elements
            a[i]=a[j];
            a[j]=tmp;
        }
        return a;
    }

    static int[] bubSort(int[] a,int size){         //simple bubble sort with comparison criteria changed
        int i,j;
        for(i=0;i<size-1;i++)
            for(j=0;j<size-i-1;j++)
                a=compare(a,j,j+1);
        return a;
    }

    //driver function
    public static void main(String[] args) {
        int n,i;
        Scanner in = new Scanner(System.in);
        System.out.print("\nEnter size of array:");
        n=in.nextInt();
        int[] ar = new int[n];
        System.out.println("Enter the array:");
        for (i=0;i<n;i++)
            ar[i]=in.nextInt();
        ar=bubSort(ar,n);
        System.out.println("Maximum num made from the array is:");
        for (i=0;i<n;i++)
            System.out.print(ar[i]);
    }
}

OUTPUT:

Enter size of array:5
Enter the array:
1 10 11 100 110
Maximum num made from the array is:
11111010100

Java Programmers can join

noreply@blogger.com (AppLord) — Fri, 03 Apr 2015 14:37:00 +0000

Are you a enthusiastic java programmer?
Would you like to share the beauty of your code with the world?
Then just message us via our facebook page facebook.com/rawjava along with your
1.gmail id
2.hackerrank username.
You shall be added to this blog after verifying your credentials.