Binary Search Tree implemented using Java ....

Binary Search Tree -

A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree.^[1]:287 (The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another. Leaves are commonly represented by a special leaf or nil symbol, a NULL pointer, etc.)

here is the code ....

       
public class BinarySearchTreeImplementation {

 public static void main(String args[]) {

  BinarySearchTree tree = new BinarySearchTree();
  tree.addNode(50);
  tree.addNode(10);
  tree.addNode(100);
  tree.addNode(20);
  tree.addNode(200);
  tree.addNode(99);
  System.out.println("Binary Search Tree after the insertion of the nodes");
  tree.printBSTPreOrder();
 }

}

class BinarySearchTree {

 Node root;

 class Node {
  int data;
  Node leftChild;
  Node rightChild;

  Node(int d) {
   data = d;
   leftChild = null;
   rightChild = null;
  }
 }

 public void addNode(int d) {
  Node new_node = new Node(d);
  Node temp;
  if (root != null) {
   temp = root;
   Node parent_node = findPositionForNodeToAdd(temp, d);
   if (parent_node.data < d)
    parent_node.rightChild = new_node;
   else
    parent_node.leftChild = new_node;

  } else {
   root = new_node;
  }
 }

 public Node findPositionForNodeToAdd(Node root, int d) {

  if (root.leftChild == null && root.rightChild == null)
   return root;
  else if (root.data >= d) {
   if (root.leftChild != null)
    return findPositionForNodeToAdd(root.leftChild, d);
   else
    return root;
  } else if (root.data < d) {
   if (root.rightChild != null)
    return findPositionForNodeToAdd(root.rightChild, d);
   else
    return root;
  }

  return null;
 }

 //Prints the binary search tree in pre order traversal
 public void printBSTPreOrder() {
  if (root == null)
   System.out.println("Binary Search Tree is empty till now");
  else {
   Node temp = root;
   preOrder(temp);
  }
 }

 private void preOrder(Node root) {
  if (root == null)
   return;
  else {
   System.out.print(root.data + " ");
   preOrder(root.leftChild);
   preOrder(root.rightChild);
  }
 }
}

       
 

Sorting a Linked List contains only 0's,1's and 2's using Java ...

Problem - Given an unsorted Linked List containing values from the set {0,1,2}                       only sort it using java. 

Here is the code ....

       

public class SortLinkedList {

 public static void main(String[] args) {

  LinkedList list = new LinkedList();
  list.push(0);
  list.push(1);
  list.push(0);
  list.push(1);
  list.push(2);
  list.push(2);
  list.push(0);
  list.push(1);
  list.push(1);
  list.push(2);
  list.push(0);

  System.out.println("Before sorting");
  list.printList();
  System.out.println();
  list.sortList();
  System.out.println("After sorting");
  list.printList();
 }

}
class LinkedList {

 private Node head;

 class Node {
  int data;
  Node next;
  Node(int d) {
   next = null;
   data = d;
  }
 }

 public void push(int d) {

  Node new_Node = new Node(d);

  new_Node.next = head;
  head = new_Node; //Adding elements at the start of linked list
 }

 public void printList() {
  Node temp = head;
  while (temp != null) {
   System.out.print(temp.data);
   temp = temp.next;
   System.out.print(" ");
  }
 }
 public void sortList() {
  int[] count = new int[3];
  count[0] = 0;
  count[1] = 0;
  count[2] = 0;
  Node temp = head;
  while (temp != null) {
   if (temp.data == 0)
    count[0]++;
   else if (temp.data == 1)
    count[1]++;
   else count[2]++;
   temp = temp.next;
  }
  temp = head;
  int i = 0;
  while (temp != null) {
   if (count[i] == 0)
    i++;
   else {
    temp.data = i;
    temp = temp.next;
    count[i]--;
   }
  }
 }
}

       
 

Sort anagram strings using Java....

Problem Statement - Given a list of strings ,sort the list in such a fashion that anagrams are always                                       adjacent to each other.

here is the code ........

       
import java.io.*;
import java.util.*;

class sortanagram {

 public static boolean anagram(String arg1, String arg2) {
  int f;
  int[] arr = new int[256];
  if (arg1.length() == arg2.length()) {
   for (int i = 0; i < arg1.length(); i++) {
    f = arg1.charAt(i);
    arr[f] = arr[f] + 1;
   }

   for (int k = 0; k < arg2.length(); k++) {
    f = arg2.charAt(k);
    arr[f] = arr[f] - 1;
   }
   for (int d = 0; d < 256; d++) {
    if (arr[d] != 0) {
     return false;
    }

   }
   return true;
  } else {
   return false;
  }

 }

 public static void main(String args[]) {

  String[] args3 = {
   "abcd",
   "save",
   "dcba",
   "dog",
   "easv",
   "god",
   "free"
  };
  String temp;
  int p;

  for (int i = 0; i < args3.length; i++) {
   p = i;
   for (int l = i + 1; l < args3.length; l++) {
    if (anagram(args3[i], args3[l]) == true) {


     p++;
     temp = args3[l];
     args3[l] = args3[p];
     args3[p] = temp;

    }

   }

  }

  for (int r = 0; r < args3.length; r++)
   System.out.println(args3[r]);

 }

}

       
 

Prime number generator using Java....

Input Format- First line of input is number of test cases    //No. of Inputs

                        Second line contains two numbers separated by space ,all prime numbers generated                             will lie between them.
               
      e.g-            2                                //No. of Test cases
                        10 100                       //First test case
                        101 200                     //Second Case

here is the code ....

       
import java.io.*;
import java.util.*;
import java.lang.Math.*;

public class PrimeNumberGenerator {
 public static void main(String[] args) {
  Scanner in = new Scanner(System.in);

  int[] primes = new int[4000];
  int numprimes = 0;

  primes[numprimes++] = 2;
  for (int i = 3; i <= 32000; i += 2) {
   boolean isprime = true;
   double cap = Math.sqrt(i) + 1.0;

   for (int j = 0; j < numprimes; j++) {
    if (j >= cap) break;
    if (i % primes[j] == 0) {
     isprime = false;
     break;
    }
   }
   if (isprime) primes[numprimes++] = i;
  }


  int T, N, M;

  T = in .nextInt();

  for (int t = 0; t < T; t++) {
   if (t > 0) System.out.println("");

   M = in .nextInt();
   N = in .nextInt();

   if (M < 2) M = 2;

   boolean[] isprime = new boolean[100001];
   for (int j = 0; j < 100001; j++) {
    isprime[j] = true;
   }

   for (int i = 0; i < numprimes; i++) {
    int p = primes[i];
    int start;

    if (p >= M) start = p * 2;
    else start = M + ((p - M % p) % p);

    for (int j = start; j <= N; j += p) {
     isprime[j - M] = false;
    }
   }

   for (int i = M; i <= N; i++) {
    if (isprime[i - M]) System.out.println(i);
   }
  }
 }
}

       
 

Optimized Bubble Sort using Java .....

Quick Logic - In bubble sort we are compairing adjacent elements, swap them if we need to and this                          will continue upto (N-1) passes .So optimized bubble sort will be most efficient if the                          array is already sorted or almost sorted.

Optimization Logic - We are checking that if two continues passes of the bubble sort are same then                            we don't have to continue further because array has already become sorted till now.

here is the code....

       
public class OptimizedBubbleSort {

 static int[] arr = {
  1,
  2,
  3,
  4,
  5,
  6,
  70,
  18,
  9
 };
 static boolean[] swapFlag = new boolean[arr.length - 1]; //to keep track that in each pass swap happens or not
 static int temp;

 public static void main(String[] args) {

  bubbleSort();
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
 }

 public static void bubbleSort() {

  for (int i = 0; i < arr.length - 1; i++) {
   for (int y = 0; y < arr.length - i - 1; y++) {
    if (arr[y] > arr[y + 1]) {
     swap(y, y + 1);
     swapFlag[i] = true;
    }
   }
   System.out.println(i + " pass");
   if (i != 0) {
    if (swapFlag[i] == false && swapFlag[i - 1] == false) //condition where we are checking that int two succesive passes
     return;
   }
  }
 }

 public static void swap(int k, int r) {
  temp = arr[r];
  arr[r] = arr[k];
  arr[k] = temp;
 }

}

       
 

Dijkstra's Algorithm using Min Heap to find shortest path from source to all other nodes in Java .....

here is the code .....

       
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class DijkstraProblem {

 static int[][] costMatrix;
 static String line;
 static String[] lineValues;
 static int totalNodes;
 static int source;
 static int[] heapHolder; //to hold the cost of path to nodes 
 static int[] nodeNameHolder; //to hold the nodes corresponding to the heap cost in heapholder
 static int heapLength;
 static int smallest;
 static int left; // left child index
 static int right; // right child index
 static int temp;
 static int reducedNode = 0;
 static int reducedNodePathCost = 1;
 static int[] deletedNode; //to hold the cost and the node number everytime we delete root node from heap 
 static int newCostViaReducedNode;


 public static void main(String[] args) throws IOException {

  String path = "C:/Users/gauravy/Desktop/matrix.txt";
  loadfile(path);
  BufferedReader gr = new BufferedReader(new InputStreamReader(System.in));
  System.out.println("Please enter the node number from where you want shortest path to all nodes ...");
  source = Integer.parseInt(gr.readLine());
  applyDijkstra(source);

  System.out.println("Shortest path from source to all other nodes is below sequentially.....");
  for (int v = 0; v < totalNodes; v++) {
   System.out.print("source to node " + v + " cost is - " + costMatrix[source][v]);
   System.out.println("");
  }


 }

 // method to load the adjacency matrix for graph from the text file
 public static void loadfile(String path) throws IOException {

  FileReader fr = new FileReader(new File(path));
  BufferedReader br = new BufferedReader(fr);

  line = br.readLine();
  lineValues = line.split(" ");
  totalNodes = lineValues.length;
  costMatrix = new int[totalNodes][totalNodes];
  heapHolder = new int[totalNodes];
  deletedNode = new int[2];
  //viaNodeHolder = new int[totalNodes];
  nodeNameHolder = new int[totalNodes];
  heapLength = lineValues.length;

  int r = 0;

  while (line != null) {
   for (int c = 0; c < totalNodes; c++) {
    costMatrix[r][c] = Integer.parseInt(lineValues[c]);

   }
   r++;
   line = br.readLine();
   if (line != null)
    lineValues = line.split(" ");
  }
  fr.close();
  br.close();
 }

 // here we are applying the Dijkstra's algorithm
 public static void applyDijkstra(int source) {

  //viaNodeHolder[0] = 0;
  //nodeNameHolder[0]=0;
  for (int y = 0; y < heapLength; y++) {
   heapHolder[y] = Integer.MAX_VALUE;
   //viaNodeHolder[y] = 0;
   nodeNameHolder[y] = y;
  }
  heapHolder[source] = 0;

  buildMinHeap();

  for (int k = 0; k < totalNodes; k++) {
   deleteRoot();

   for (int p = 0; p < heapLength; p++) {
    newCostViaReducedNode = deletedNode[reducedNodePathCost] + costMatrix[deletedNode[reducedNode]][nodeNameHolder[p]];

    if (newCostViaReducedNode < heapHolder[p]) {
     heapHolder[p] = newCostViaReducedNode;
     costMatrix[source][nodeNameHolder[p]] = newCostViaReducedNode;
    }
    min_Heapify(0);
   }
  }
 }

 public static void buildMinHeap() {
  for (int p = heapHolder.length / 2 - 1; p >= 0; p--) {
   min_Heapify(p);
  }
 }

 // min heapify algorithm implemented here
 public static void min_Heapify(int p) {
  left = leftChild(p);
  right = rightChild(p);

  if ((left < heapLength) && (heapHolder[left] < heapHolder[p]))
   smallest = left;
  else
   smallest = p;

  if ((right < heapLength) && (heapHolder[right] < heapHolder[smallest]))
   smallest = right;

  if (smallest != p) {
   swap(smallest, p);
   min_Heapify(smallest);
  }
 }

 // returns index of left child
 public static int leftChild(int k) {
  return (2 * k + 1);
 }

 // returns of right child
 public static int rightChild(int i) {
  return (2 * i + 2);
 }

 // for swapping purpose
 public static void swap(int a, int b) {

  temp = heapHolder[a];
  heapHolder[a] = heapHolder[b];
  heapHolder[b] = temp;

  temp = nodeNameHolder[a];
  nodeNameHolder[a] = nodeNameHolder[b];
  nodeNameHolder[b] = temp;
 }

 // for deletion of root node from heap
 public static void deleteRoot() {

  deletedNode[reducedNode] = nodeNameHolder[0];
  deletedNode[reducedNodePathCost] = heapHolder[0];

  heapHolder[0] = heapHolder[heapLength - 1];
  //viaNodeHolder[0] = viaNodeHolder[heapLength - 1];
  nodeNameHolder[0] = nodeNameHolder[heapLength - 1];

  heapLength--;
  min_Heapify(0);
 }

}

       
 

Max Heap using Java.....

here is the code...

       
public class BuildMaxHeapProblem {
 static int[] heap = {
  80,
  90,
  32,
  1,
  40,
  50,
  45,
  22,
  12,
  23,
  33
 };
 static int largest;
 static int left; //left child index
 static int right; //right child index
 static int temp;

 public static void main(String[] args) {
  buildMaxHeap();
  for (int k: heap) {
   System.out.print(k);
   System.out.print(" ");
  }
 }
 public static void buildMaxHeap() {
  for (int p = heap.length / 2 - 1; p >= 0; p--) {
   max_Heapify(p);
  }
 }
 public static void max_Heapify(int p) {
  left = leftChild(p);
  right = rightChild(p);

  if ((left < heap.length) && (heap[left] > heap[p]))
   largest = left;
  else largest = p;

  if ((right < heap.length) && (heap[right] > heap[largest]))
   largest = right;

  if (largest != p) {
   swap(largest, p);
   max_Heapify(largest);
  }
 }
 public static int leftChild(int k) {
  return (2 * k + 1);
 }
 public static int rightChild(int i) {
  return (2 * i + 2);
 }
 public static void swap(int a, int b) {
  temp = heap[a];
  heap[a] = heap[b];
  heap[b] = temp;
 }

}