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