Binary Search Tree in Java

public class BinarySearchTree<Key extends Comparable<Key>, Value> {
    Node<Key, Value> root;
    public void addNode(Key key, Value val) {
        addNode(this.root, key, val);
    }
    public Node addNode(Node<Key, Value> node, Key key, Value value) {
        if (node == null) {
            Node<Key, Value> nodeTemp = new Node<Key, Value>(key, value);
            if (this.root == null) {
                this.root = nodeTemp;
            }
            return nodeTemp;
        }
        int compareTo = key.compareTo((Key) node.keyT);
        if (compareTo < 0) {
            node.left = addNode(node.left, key, value);
        } else if (compareTo > 0) {
            node.right = addNode(node.right, key, value);
        } else {
            node.keyT = key;
            node.value = value;
        }
        return node;
    }
    Node<Key, Value> getNode(Key key) {
        Node<Key, Value> node = this.root;
        while (node != null) {
            int cmp = key.compareTo((Key) node.keyT);
            if (cmp < 0) {
                node = node.left;
            } else if (cmp > 0) {
                node = node.right;
            } else if (cmp == 0) {
                return node;
            }
        }
        return null;
    }
    private static void printInOrder(Node<Integer, String> node) {
        if (node == null) {
            return;
        }
        printInOrder(node.left);
        System.out.println(node.value);
        printInOrder(node.right);
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        BinarySearchTree<Integer, String> bst = new BinarySearchTree<Integer, String>();
        bst.addNode(new Integer(7), "seven");
        bst.addNode(new Integer(8), "eight");
        bst.addNode(new Integer(9), "nine");
        bst.addNode(new Integer(5), "five");
        bst.addNode(new Integer(6), "six");
        bst.addNode(new Integer(4), "four");
        bst.addNode(new Integer(3), "three");
        bst.addNode(new Integer(10), "ten");
        bst.addNode(new Integer(2), "two");
        bst.addNode(new Integer(1), "one");
        printInOrder(bst.root);
    }
}
class Node<T extends Comparable<T>, Value> {
    T keyT;
    Value value;
    Node<T, Value> left;
    Node<T, Value> right;
    Node(T key, Value val) {
        this.keyT = key;
        this.value = val;
    }
}

Quick Sort in Java

 private static void quickSort(Integer[] toSortArray, int low, int high) {
        if (low >= high)
            return;
        int k = partition(toSortArray, low, high);
        quickSort(toSortArray, low, k - 1);
        quickSort(toSortArray, k + 1, high);
    }
    /**
     * given a number index low, it partitions array 
     * such that all numbers less than numbers[]low] are left
     * and greater are right
     * @param numbers
     * @param low
     * @param high
     * @return
     */
    private static int partition(Integer[] numbers, int low, int high) {
        int leftIndex = low;
        int rightIndex = high + 1;
        while (true) {            
            //find left index to swap
            while (numbers[++leftIndex] < numbers[low]) {
                if (leftIndex == high) {
                    break;
                }
            }
            //find right index to swap
            while (numbers[low] < numbers[--rightIndex]) {
                if (rightIndex == low) {
                    break;
                }
            }
            // pointers cross
            if (leftIndex >= rightIndex)
                break;
            //swap
            swap(leftIndex, rightIndex, numbers);
        }
        swap(low, rightIndex, numbers);
        return rightIndex;
    }
    private static void printArray(Integer[] toSortArray) {
        for (int i = 0; i < toSortArray.length; i++) {
            System.out.print(toSortArray[i] + " ");
        }
        System.out.println(" ");
    }
    /**
     * swap 2 numbers at the index
     * 
     * @param minIndex
     * @param index
     * @param numbers
     */
    private static void swap(int minIndex, int index, Integer[] numbers) {
        Integer temp = numbers[minIndex];
        numbers[minIndex] = numbers[index];
        numbers[index] = temp;
    }

Merge Sort in Java

  private static void sortList(Integer[] toSortArray) {
        Integer[] sortedArray = new Integer[toSortArray.length];
        mergeSortList(toSortArray, sortedArray, 0, toSortArray.length - 1);
    }
    private static void mergeSortList(Integer[] toSortArray, Integer[] sortedArray, int low, int high) {
        if (low >= high)
            return;
        int mid = (high + low) / 2;
        mergeSortList(toSortArray, sortedArray, low, mid);
        mergeSortList(toSortArray, sortedArray, mid + 1, high);
        mergeResults(toSortArray, sortedArray, low, mid, high);
        printArray(toSortArray);
    }
    private static void mergeResults(Integer[] toSortArray, Integer[] sortedArray, int low, int mid, int high) {
        for (int index = low; index <= high; index++) {
            sortedArray[index] = toSortArray[index];
        }
        int leftIndex = low;
        int rightIndex = mid + 1;
        for (int k = low; k <= high; k++) {
            System.out.println(leftIndex + " " + rightIndex + " " + k);
            if (leftIndex > mid) {
                toSortArray[k] = sortedArray[rightIndex++];
            } else if (rightIndex > high) {
                toSortArray[k] = sortedArray[leftIndex++];
            } else if (sortedArray[leftIndex] < sortedArray[rightIndex]) {
                toSortArray[k] = sortedArray[leftIndex++];
            } else {
                toSortArray[k] = sortedArray[rightIndex++];
            }
        }
    }

 

Time Complexity: n log n

Insertion Sort in Java

Before Sorting, Input :0 10 2 9 3 8 1 6 5 7 4   the first element is sorted here
0 10 2 9 3 8 1 6 5 7 4    first 2 elements are sorted
0 2 10 9 3 8 1 6 5 7 4   and so on….
0 2 9 10 3 8 1 6 5 7 4 
0 2 3 9 10 8 1 6 5 7 4 
0 2 3 8 9 10 1 6 5 7 4 
0 1 2 3 8 9 10 6 5 7 4 
0 1 2 3 6 8 9 10 5 7 4 
0 1 2 3 5 6 8 9 10 7 4 
0 1 2 3 5 6 7 8 9 10 4 
0 1 2 3 4 5 6 7 8 9 10 
After Sorting, output :0 1 2 3 4 5 6 7 8 9 10 

 

 

 /**
     * every element before the index is sorted. so select the number at the
     * index location and put it in appropriate position
     * 
     * @param numbers
     */
    private static void sortList(Integer[] numbers) {
        for (int index = 0; index < numbers.length; index++) {
            for (int sortIndex = index; sortIndex > 0; sortIndex--) {
                if (numbers[sortIndex] < numbers[sortIndex - 1]) {
                    swap(sortIndex, sortIndex - 1, numbers);
                } else {
                    break;
                }
            }
            printArray(numbers);
        }
    }
    /**
     * swap 2 numbers at the index
     * 
     * @param indexOne
     * @param indexTwo
     * @param numbers
     */
    private static void swap(int indexOne, int indexTwo, Integer[] numbers) {
        Integer temp = numbers[indexOne];
        numbers[indexOne] = numbers[indexTwo];
        numbers[indexTwo] = temp;
    }

Selection Sort in Java

• Find the smallest entry for an Index
• Swap it with the index element do this iteratively till the end of the array

Complexity: (n power 2)/2  comparisions & n exchanges

 

 

  /**
     * find the minimum in the series and swap it to the index 
     * @param numbers
     */
    private static void sortList(Integer[] numbers) {
        for (int index = 0; index < numbers.length; index++) {
            int minIndex = findMininRest(index, numbers);
            if (minIndex != index) {
                swap(minIndex, index, numbers);
                printArray(numbers);
            }
        }
    }
    /**
     * swap 2 numbers at the index 
     * @param minIndex
     * @param index
     * @param numbers
     */
    private static void swap(int minIndex, int index, Integer[] numbers) {
        Integer temp = numbers[minIndex];
        numbers[minIndex] = numbers[index];
        numbers[index] = temp;
    }
    /**
     * find the minimum in the rest of the series
     * 
     * @param index
     *            the current index to fill
     * @param numbers
     *            all the numbers
     * @return returns the index of the minimum element in the rest series from
     *         index
     */
    private static int findMininRest(int index, Integer[] numbers) {
        int currentMin = index;
        for (int restIndex = index + 1; restIndex < numbers.length; restIndex++) {
            if (numbers[currentMin] > numbers[restIndex]) {
                currentMin = restIndex;
            }
        }
        return currentMin;
    }

Trace of the sort per Iteration

0 10 2 9 3 8 1 6 5 7 4 INPUT

0 1 2 9 3 8 10 6 5 7 4
0 1 2 3 9 8 10 6 5 7 4
0 1 2 3 4 8 10 6 5 7 9
0 1 2 3 4 5 10 6 8 7 9
0 1 2 3 4 5 6 10 8 7 9
0 1 2 3 4 5 6 7 8 10 9

0 1 2 3 4 5 6 7 8 9 10 OUTPUT

Recursively print Permutations of a String

        recursivelyReverse("", "helloWorld");
   
    private static void recursivelyReverse(String first, String second) {
        if (second.length() == 0) {
            System.out.println(first);
            return;
        }
        for (int index = 0; index < second.length(); index++) {
            recursivelyReverse(first + second.charAt(index), second.substring(0, index) + second.substring(index + 1));
        }
    }

Recursively reverse a linked list

private static Node recurReverseLinkedList(Node firstNode) {
        if (firstNode == null || firstNode.next == null) {
            return firstNode;
        }
        
        Node secondNode = firstNode.next; // the new head node to be reversed
        firstNode.next = null; // de-link the node from the list
        Node previousFirstNode = recurReverseLinkedList(secondNode); //reverse rest
        secondNode.next = firstNode; //the second node next will be first node
        return previousFirstNode; 
    }

Recursive Sum of Linked list node values

   private static int recursiveSum(Node head) {
        //base case
        if (head.next == null) {
            return head.value;
        }
        //general case
        return head.value + recursiveSum(head.next);
    }

Reversing a Linked List

    private static void reverseLinkedList(MyLinkedList linkedList) {
        Node current = linkedList.head;
        Node previous = null;
        Node next = null;
        while (current != null) {
            next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }
        linkedList.head = previous;
    }

Factorial Recursive in Java

    private static int factorial(int i) {
        // base case
        if (i == 0 || i == 1) {
            return 1;
        } else { // general case
            return i * factorial(i - 1);
        }
    }