Binary search tree implementation in Java using generics

Binary tree is a data structure in which each node has atmost 2 child subtree's, each of which is a binary tree. The child subtree's are called left and right.

A Binary search tree(BST) is a binary tree in which each node has a value, the node values of the left subtree contains only values less than the node value and the node values of the right subtree contains only values greater than the node value. The search tree could allow duplicate values, depending on the implementation.

Following is my implementation of binary search tree in Java with generics.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * Implements an unbalanced binary search tree.
 */
public class MyTree<T extends Comparable<T>> {
    Node<T> root;
    
    /**
     * Construct the tree.
     */
    public MyTree(T elem) {
        root = new Node<T>(elem,null,null);
    }
    
    /**
     * Insert into the tree.
     * @param elem is the item to insert.
     * @throws IllegalArgumentException if elem is already present.
     */
    public void add(T elem) {
        Node<T> node = new Node<T>(elem,null,null);
        insertNode(root,node);
    }
    
     /**
     * Internal method to insert into a subtree.
     * @param subTree is the subtree.
     * @param newNode is the new node to be inserted.
     * @return the new subtree.
     * @throws IllegalArgumentException if newNode is already present.
     */
    private Node<T> insertNode(Node<T> subTree, Node<T> newNode) {
        
        if (subTree == null) {
            subTree = newNode;
        } else if ((subTree.elem).compareTo(newNode.elem) < 0){
                subTree.rightChild = insertNode(subTree.rightChild, newNode);
        } else if ((subTree.elem).compareTo(newNode.elem) > 0){
                subTree.leftChild = insertNode(subTree.leftChild, newNode);
        } else {
            throw 
                new IllegalArgumentException("Duplicate Element " + newNode.elem);
        }
        return subTree;
    }
    
    /**
     * Remove from the tree.
     * @param item is the item to remove.
     * @throws IllegalArgumentException if item is not found.
     */
    public void delete(T item) {
        this.deleteNode(root,item);
    }
    
     /**
     * Internal method to delete a node.
     * @param subTree is the subtree.
     * @param item is the item to be deleted.
     * @return the new subtree.
     * @throws IllegalArgumentException if the item is not present.
     */
    private Node<T> deleteNode(Node<T> subtree,  T item) {
        //Search for the node first 
        if (subtree != null) {
            if ((subtree.elem).compareTo(item) < 0) {
                subtree.rightChild = deleteNode(subtree.rightChild, item);
            } else if ((subtree.elem).compareTo(item) > 0) {
                subtree.leftChild = deleteNode(subtree.leftChild, item);
            } else {
                /* Found a match.
                 * There are 3 possibilities:
                 * Node is leaf: 
                 *     Easy, Just delete the node but this is implicitly
                 * handled as part of node has 1 child (see below)
                 * Node has 1 child: 
                 *     Delete the node and put the child node in its place
                 * Node has 2 children: 
                 *     Find the leftmost child in the right subtree, 
                 *     replace the node to be deleted with this child.
                 *     Then delete that child node.
                 */
                if ((subtree.leftChild != null) && (subtree.rightChild != null)) {
                    //Node has 2 children
                    //Find the leftmost child of the right subtree and
                    //make it the current node, then delete the
                    //leftmost child of the right subtree
                    Node<T> node = findLeftmostChild(subtree.rightChild);
                    subtree.elem = node.elem;
                    subtree.rightChild = deleteNode(subtree.rightChild,node.elem);
                } else if (subtree.leftChild != null) {
                    //Node has only 1 child i.e. left child
                    subtree = subtree.leftChild;
                } else {
                    //Node can either have no children or just have 1 right child
                    subtree = subtree.rightChild;    
                }
            }
            
        } else{
            //No match
            throw new IllegalArgumentException("No such element");
        }
        return subtree;
    }
    
    /**
     * Internal method to find the leftmost child.
     * @param subtree is the subtree.
     * @return the leftmost child.
     */
    private Node<T> findLeftmostChild(Node<T> subtree){
        assert (subtree != null);
        while (subtree.leftChild != null) {
            subtree = subtree.leftChild;
        }
        return subtree;
    }
    
    /**
     * Method to traverse the tree in depth first order.
     * @return the List of elements in the tree in depth first order.
     */
    public List<T> depthFirstTraversal() {
        List<T> l = new ArrayList<T>();
        Stack<Node<T>> s = new Stack<Node<T>>();
        s.push(root);
        while (!s.isEmpty()){
            Node<T> node = s.pop();
            l.add(node.elem);
            if (node.rightChild != null) {
                s.push(node.rightChild);
            }
            if (node.leftChild != null) {
                s.push(node.leftChild);
            }
        }
        return l;
    }
    
    /**
     * Method to traverse the tree in breadth first order
     * @return the List of elements in the tree in breadth first order.
     */
    public List<T> breadthFirstTraversal() {
        List<T> l = new ArrayList<T>();
        Queue<Node<T>> q = new LinkedList<Node<T>>();
        q.add(root);
        while (!q.isEmpty()) {
            Node<T> node = q.poll();
            l.add(node.elem);
            if (node.leftChild != null) {
                q.add(node.leftChild);
            } 
            if (node.rightChild != null) {
                q.add(node.rightChild);
            }
        }
        return l;
    }
    
    /**
     * Method to find an item in a subtree.
     * @param item is item to search for.
     * @return node containing the matched item.
     */
    public Node<T> findNode(T item) {
        if (item == null) return null;
        Node<T> current = root;
        while ((current.elem).compareTo(item) != 0) {
            if ((current.elem).compareTo(item) > 0) {
                current = current.leftChild;
            } else if ((current.elem).compareTo(item) < 0) {
                current = current.rightChild;
            }
            if (current == null) return null;
        }
        return current;
        
    }    
    
    //Test it
    public static void main(String[] args) {
        MyTree<Integer> tree = new MyTree<Integer>(20);
        tree.add(30);
        tree.add(10);
        tree.add(15);
        tree.add(24);
        tree.add(36);
        //tree.add(30);
        
        List<Integer> l = tree.depthFirstTraversal();
        System.out.println("Depth First Order");
        printTree(l);
        l = tree.breadthFirstTraversal();
        System.out.println("Breadth First Order");
        printTree(l);
        
        tree.delete(30);
        System.out.println("Tree after deleting a node");
        l = tree.depthFirstTraversal();
        printTree(l);
    }
    
    //Method to print tree
    public static <T> void printTree(List<T> l) {
        for(T i: l) {
            System.out.println(i);
        }
    }

}

/**
 * Basic node stored in binary search trees
 */
class Node<T extends Comparable<T>>{
    T elem;
    Node<T> leftChild;
    Node<T> rightChild;
    
    Node(T elem, Node<T> left, Node<T> right){
        this.elem = elem;
        leftChild = left;
        rightChild = right;
    }
}

Note:
I did not use google-code-prettify to highlight my code as it eats up types (generic and actual) in the angle braces.
More information about BST can be found here.

Selection Sort in Python

Selection sort is a very simple sorting mechanism. It looks through the remaining items in the input to find the least one and moves it to its final position. It is an in-place sort and has a complexity of O(n²) . Here is an implementation of it in Python.

import types

def doSelectionSort(input):
    "Check for a few simple error conditions"
    if input == None:
        raise Exception("Input cannot be null")
    if not type(input) is types.ListType:
        raise Exception("Input can only be a List")

    "Do the sort"
    length = len(input)
    if length <= 1:         "Input is already sorted"         return     i = 0     while i < smallest =" i" j =" i" smallest =" j" temp =" input[i]" a =" [3,6,8,2,0,9,5,89,9]" b =" []" c =" (3,4)">

Here is the ouput:
[0, 2, 3, 5, 6, 8, 9, 9, 89]
[]
Input can only be a List

Quicksort implementation in Java

Quicksort is a well known sorting algorithm. You can find more information about it here. Following is an implementation of Quicksort in Java with generics.

public class QuickSort {

    /**
     * Quicksort using Java generics
     * @param a an array of Comparable items.
     */
    public static <T extends Comparable<T>> 
                        void doQuickSort(T[] a) {
        if (a == null) {
            throw new 
                IllegalArgumentException("Input Array cannot be null");
        }
        int length = a.length;
        if (length == 1) return;
        doQuickSort(a, 0, length-1);
    }
    
    /**
     * Actual quicksort implementation using 
     * median of 3 partitioning.
     * @param a an array of Comparable items.
     * @param left the left index of the subarray.
     * @param right the right index of the subarray.
     */
    private static <T extends Comparable<T>> void 
                        doQuickSort(T[] a, int left, int right) {
        
        //Base case
        if (left >= right) return;
        
        //Choose the pivot using median of 3 partitioning
        //using the following 2 steps
        //First step: find the center
        int center = (left+right)/2;
        //Second step: sort left, center and right
        if (a[left].compareTo(a[center]) > 0) {
            swap(a, left, center);
        }
        if (a[left].compareTo(a[right]) > 0) {
            swap(a, left, right);
        }
        if (a[center].compareTo(a[right]) > 0) {
            swap(a, center, right);
        }    
        //Third Step: 
        //Got the pivot and it is at the center. 
        //Move it to the end of the array.
        swap(a,center,right-1);
        int pivot = right-1;
        
        //Partition the array 
        int i = left,j = right - 2;
        if (j >= 0) {
            for(;;) {
                while (a[i].compareTo(a[pivot])< 0) {
                i++;
                }
                while(a[j].compareTo(a[pivot]) > 0) {
                j--;
                }
                if (i >= j) break;
                swap(a,i,j);
            }
        }
        //Put the pivot at ith position of the array
        swap(a,i,right-1); 
        //Now all the elements to the right of i are less than 
        //it and all the elements to the left of i are greater
        //than it. So partition the array and 
        //recursively call quicksort on the left and right partition
        doQuickSort(a, left, i-1);
        doQuickSort(a, i+1, right);
        
    }
    
    /**
     * Internal method to swap to elements in an array.
     * @param a an array of objects.
     * @param left the index of the first object.
     * @param right the index of the second object.
     */
    private static <T extends Comparable<T>> 
                    void swap(T[] a, int left, int right) {
        T temp = a[left];
        a[left] = a[right];
        a[right] = temp;
    }
    
    //Test it
    public static void main(String[] args) {
        Integer[] input = {5,14,16,2,17,1,8,6,0,9};
        doQuickSort(input);
        printArray(input);
        String[] str = new String[]{"adc","abc", "acd", "aaa"};
        doQuickSort(str);
        printArray(str);
    }
    
    /**
     * Internal method to print the elements in an array.
     * @param a an array of objects.
     */
    private static <T extends Comparable<T>> 
                        void printArray(T[] a) {
        for (T elem: a) {
            System.out.println(elem);
        }
    }

}

Output on running the above program:
0
1
2
5
6
8
9
14
16
17
aaa
abc
acd
adc

Insertion sort in Java using generics

Insertion sort
It looks at the next item of the input and inserts it into its correct position in the "already sorted" previous items of the input. Here is the code for it using Java Generics.

public class MyInsertionSort {
    
    public <T extends Comparable<T>> void doInsertionSort(T[] input) {
        
        if (input == null) {
            throw new RuntimeException("Input array cannot be null");
        }
        int length = input.length;
        //Already sorted
        if (length == 1) return;
        int i,j;
        T temp;
        for (i = 1; i < length; i++) {
            //Store the current element
            temp = input[i]; 
            //Compare the current element with 
            //the partially sorted group
            //to see if its in the correct position 
            for (j = i; (j > 0 && (temp.compareTo(input[j-1]) < 0)); j--){
                //The current element is not in
                // its correct position in the
                //partially sorted list. Move 
                //the larger item one place 
                //to right and make space
                // for the current element
                input[j] = input[j-1];
            }            
            //Found the correct position 
            //for the current element
            //in the partially sorted group. 
            //So move it to its correct place.
            input[j] = temp;
        }
        
    }

Test it.

public class MyMain {
    
    public static <T> void printArray(T[] input) {
        for(T elem: input) {
            System.out.print(elem);
            System.out.print(" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        
        String[] s = {"Hello", "World", "Hello"};
        Integer[] intArray = {1,4,9,0,8,7,9,6};
        
        //Test insertionsort
        MyInsertionSort is = new MyInsertionSort();
        is.doInsertionSort(s);
        is.doInsertionSort(intArray);
        printArray(s);
        printArray(intArray); 

        
    }

}

Running it produces the following output:
Hello Hello World
0 1 4 6 7 8 9 9

Efficiency of Insertion sort
In the first pass we will have max of 1 comparision,in the second one we will have a max of 2 comparisions and so on. So this is
1+2+3+....(n-1) and it sums up to roughly n(n-1)/2 i.e. approximately n². So the running time for random data it is O(n²) but for already sorted data it will never enter the second for loop, so it will run in O(n) .

Analysis
The insertion sort is not a good sort for large inputs of data. More information on Insertion sort can be found here.