Binary Search Tree using Collections

BinaryTreeTest.java

/*
 * Reference : Introduction to Java Programming Liang 
 * 
 */

import java.util.ArrayList;
import java.util.Iterator;

public class BinaryTreeTest {
	public static void main(String[] args){
	String[] names = {"micheal","manoj","dinesh","carmelita","uma","vinu","victory"};
	BinaryTree<String> stringTree = new BinaryTree<String>(names);
	System.out.println("Inorder : ");
	stringTree.inorder();
	System.out.println("\n"+stringTree.FindPredecessor("dinesh"));
	}
}

interface Tree<E extends Comparable<E>>{
	/*Returns true if the element e is found successfully*/
	public boolean search(E e);
	/*Returns true if the element e is inserted successfully*/
	public boolean insert(E e);
	/*Returns true if the element e is deleted successfully*/
	public boolean delete(E e);
	/* Prints the inorder traversal of the tree*/
	public void inorder();
	/*Prints the postorder traversal of the tree*/
	public void postorder();
	/*Prints the preorder traversal of the tree*/	
	public void preorder();
	/*Returns the total number of nodes in the tree*/
	public int getSize();
	/*Returns true if the tree is empty */
	public boolean isEmpty();
	/*Returns the iterator to traverse through the nodes of the tree*/
	public Iterator<E> iterator();
}

abstract class AbstractTree<E extends Comparable<E>> implements Tree<E>{
	public void inorder(){
		
	}
	public void preorder(){
		
	}
	public void postorder(){
		
	}
	public boolean isEmpty(){
		return getSize()==0;
	}
	public Iterator<E> iterator(){
		return null;
	}
}

class BinaryTree<E extends Comparable<E>> extends AbstractTree<E>{
	
	protected TreeNode<E> root = null;
	protected int size = 0;
	
	public BinaryTree(){
	}
	
	/*Creates a BST from an array of elements*/
	public BinaryTree(E[] objects){
		for(int i=0;i<objects.length; i++){
			insert(objects[i]);
		}
	}
	
	public static class TreeNode<E>{
		E element;
		TreeNode<E> left;
		TreeNode<E> right;
		
		public TreeNode(E e){
			element=e;
		}
	}

	
	/*Creates and returns a new TreeNode*/
	protected TreeNode<E> createNewNode(E e){
		return new TreeNode<E>(e);
	}
	
	/*Returns the minimum Element in the tree(Left Most)*/
	public E FindMin(){
		return FindMin(root);
	}
	
	
	public E FindMin(TreeNode<E> root){
		TreeNode<E> current = root;
		while(current.left!=null){
			current=current.left;
		}
		return current.element;
	}
	
	/*Returns the maximum element in the tree (Right Most) */
	public E FindMax(){
		return FindMax(root);
	}
	
	public E FindMax(TreeNode<E> root){
		TreeNode<E> current = root;
		while(current.right!=null){
			current=current.right;
		}
		return current.element;
	}
	
	/* Find and return the node in the tree*/
	public TreeNode<E> FindNode(E e){
		TreeNode<E> current = root;
		while(current!=null){
			if(e.compareTo(current.element)<0)
			{
				current = current.left;
			}
			else if(e.compareTo(current.element)>0)
			{
				current = current.right;
			}
			else
				break;  //Element found
		}
		return current;
		
	}
	
	/* Find and return the node in the tree*/
	public TreeNode<E> FindParent(TreeNode<E> node){
		if(node == null)return null;
		E e = node.element;
		TreeNode<E> current = root;
		TreeNode<E> parent = null;
		while(current!=null){
			if(e.compareTo(current.element)<0)
			{
				parent=current;
				current = current.left;
			}
			else if(e.compareTo(current.element)>0)
			{
				parent = current;
				current = current.right;
			}
			else
				break;  //Element found
		}
		return parent;
		
	}
	
	/*Given node, find the node with the smallest node greater than x*/
	public E FindSuccessor(E e){
		TreeNode<E> current = FindNode(e);
		TreeNode<E> parent = FindParent(current);
		TreeNode<E> successor = null;
		
		if(current == null) return null; // Element not found
		
		if(current.right!=null){
			return FindMin(current.right);
		}
		else{
			successor = parent;
			while(successor!=null && current==successor.right){
				current=successor;
				successor = FindParent(successor);
			}
			return successor.element;
		}
	
	}
	
	/*Given node, find the node with the greatest node smaller than x*/
	public E FindPredecessor(E e){
		TreeNode<E> current = FindNode(e);
		TreeNode<E> parent = FindParent(current);
		TreeNode<E> predecessor = null;
		
		if(current == null) return null; // Element not found
		
		if(current.left!=null){
			return FindMax(current.left);
		}
		else{
			predecessor = parent;
			while(predecessor!=null && current==predecessor.left){
				current=predecessor;
				predecessor = FindParent(predecessor);
			}
			return predecessor.element;
		}
	
	}
	
	@Override
	public boolean search(E e) {
		TreeNode<E> current = root;
		while(current!=null){
			if(e.compareTo(current.element)<0)
				current=current.left;
			else if(e.compareTo(current.element)>0)
				current=current.right;
			else 
				return true; //Element found
		
		}
		return false;
	}

	@Override
	public boolean insert(E e) {
		if(root==null){
			root = createNewNode(e);
		}
		else{
			TreeNode<E> parent = null;
			TreeNode<E> current = root;
			while(current!=null){
				if(e.compareTo(current.element)<0){
					parent = current;
					current = current.left;
				}
				else if(e.compareTo(current.element)>0){
					parent = current;
					current=current.right;
				}
				else 
					return false;
			}
			if(e.compareTo(parent.element)<0)
				parent.left=createNewNode(e);
			else 
				parent.right = createNewNode(e);
		}
		size++;
		return true;
	}
	/*Helper function for In order*/
	public void inorder(){
		inorder(root);
	}
	/* In order traversal of the tree from the node root */
	protected void inorder(TreeNode<E> root){
		if(root==null)return;
		inorder(root.left);
		System.out.print(root.element+" ");
		inorder(root.right);
	}
	
	/*Pre order Traversal of the tree*/
	public void preorder(){
		preorder(root);
	}
	public void preorder(TreeNode<E> root){
		if(root==null) return;
		System.out.print(root.element+" ");
		preorder(root.left);
		preorder(root.right);
	}
	
	/*Post order traversal of the tree*/
	
	public void postorder(){
		postorder(root);
	}
	public void postorder(TreeNode<E> root){
		if(root==null) return;
		postorder(root.left);
		postorder(root.right);
		System.out.print(root.element+" ");
	}
	
	/*Default Iterator*/
	public Iterator<E> iterator(){
		return inorderIterator();
	}
	
	/*Inorder Iterator*/
	public Iterator<E> inorderIterator(){
		return new InorderIterator();
	}
	
	public ArrayList<TreeNode<E>> path(E e){
		ArrayList<TreeNode <E>> list = new ArrayList<TreeNode<E>>();
		TreeNode<E> current = root;
		while(current!=null){
			list.add(current);
			if(e.compareTo(current.element)<0)
				current=current.left;
			else if(e.compareTo(current.element)>0)
				current = current.right;
			else
				break;
		}
		return list;
	}
	
	/*Iterator class for Tree*/
	class InorderIterator implements Iterator<E>{
		private ArrayList<E> list = new ArrayList<E>();
		private int current = 0;
		
		public InorderIterator(){
			inorder();
		}
		
		public void inorder(){
			inorder(root);
		}
		
		public void inorder(TreeNode<E> root){
			if(root==null)return;
			inorder(root.left);
			list.add(root.element);
			inorder(root.right);
		}
		
		

		@Override
		public boolean hasNext() {
			if(current<list.size())
				return true;
			return false;
		}

		@Override
		public E next() {
			return(list.get(current));
		}

		@Override
		public void remove() {
			delete(list.get(current));
			list.clear();
			inorder();
		}
		
	}


	@Override
	public boolean delete(E e) {
		TreeNode<E> current = root;
		TreeNode<E> parent = null;
		while(current!=null){
			if(e.compareTo(current.element)<0)
			{
				parent=current;
				current = current.left;
			}
			else if(e.compareTo(current.element)>0)
			{
				parent = current;
				current = current.right;
			}
			else
				break;  //Element found
		}
		
		if(current == null)
			return false; //Element not found
		
		//Case 1: Current has no left Child, then connect the parent with the left child
		
		if(current.left == null){
			if(parent==null){
				root = current.right;
			}
			else{
				if(e.compareTo(parent.element)<0)
					parent.left = current.right;
				else
					parent.right = current.right;
			}
		}
		/*Case 2: When current has left child
		 * Locate the right most in the left subtree and its parent
		 * 
		 */
		else{
			TreeNode<E> rightMost = current.left;
			TreeNode<E> parentRightmost = current;
			
			while(rightMost.right!=null){
				parentRightmost = rightMost;
				rightMost = rightMost.right; // keep going to right
			}
			//Copy the element of right most to current
			current.element = rightMost.element;
			
			if(parentRightmost == rightMost.right){
				parentRightmost.right = rightMost.left;
			}
			else //Special case where parent is current
				parentRightmost.left = rightMost.left;
			
		}
		size--;
		return true;
	}

	@Override
	public int getSize() {
		return size;
	}
	
	public TreeNode<E> getRoot(){
		return root;
	}
	
	/*Clears all the elements in the tree*/
	public void clear(){
		root=null;
		size=0;
	}
	
}