JAVA program to help jerry find cheese

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.

1. Start with the target
2. If the cell is not legal (if it is out of maze or the cell is a wall) return false
3. If starting point has reached return true 
4. else make the cell a wall(to avoid coming back to the same path from any other instant) and
5. 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

[Read more]

JAVA program to print all permutations of a string

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

[Read more]

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

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

[Read more]

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

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:

1. Start with first digit 1 to 9
2. 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.
3. 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

[Read more]

JAVA program to find sibling of parent of a given node

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());
    }

}

[Read more]

JAVA program to build a tree from inorder and postorder traversals

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);
    }
}

[Read more]

JAVA program to build a tree from inorder and preorder traversals

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);
    }  
}

[Read more]

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

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

[Read more]

JAVA program to convert an array to binary tree

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   

[Read more]

JAVA program to convert a sorted array to BST

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   

[Read more]

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

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

[Read more]

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

ALGORITHM:

        We have 3 types of tree traversals

1. Preorder traversal
2. Inorder traversal
3. 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   

[Read more]

JAVA program to print ancestors of a node in a BST

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:

1. if current node is the required node print the node
2. if current node is greater than required node goto step 1 for left subtree
3. 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

[Read more]

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

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 .

1. start with the root node with limits positive infinity and negative infinity
2. return true if reached the leaf
3. 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.
4. 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....");
    }
}

[Read more]

JAVA program to solve N Queens problem

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.

1. Start with first column
2. If all queens are placed return true
3. 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.
4.  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...");
        }
    }
}

[Read more]