BinarySearchTree.java

import java.util.Collection;
import java.util.List;


public class BST<T extends Comparable<T>> {
  
	private Node<T> root;
	private int size;
	public enum Side { LEFT, RIGHT };
	
	public BST()
	{
		root = null;
		size = 0;
	}
	
	/**
	 * Adds a data entry to the BST
	 * 
	 * null is positive infinity
	 * 
	 * @param data The data entry to add
	 */
	public void add(T data) {
		Node<T> temp = root;
		Node<T> parent = findParent(data, temp);
		
		// Slightly inefficient because we are comparing data to the parent's data in both add() and findParent(), should be fixed later
		if (parent == null)
		{
			root = new Node<T>(data);
		}
		else if (data == null || (parent.getData() != null && parent.getData().compareTo(data) < 0))
		{
			parent.setRight(new Node<T>(data));
		}
		else
		{
			// Using else because we aren't tested on duplicates
			parent.setLeft(new Node<T>(data));
		}
		size++;
		
	}
	
	private Node<T> findParent(T data, Node<T> root)
	{
		if (root == null) return null;
		
		// In the case where we reach a node with null data (on the far right of the tree)
		if (root.getData() == null) return root;
		
		if (data == null || root.getData().compareTo(data) < 0)
		{
			// data is greater than root
			if (root.getRight() != null)
			{
				return findParent(data, root.getRight());
			}
		}
		
		if (data != null && root.getData().compareTo(data) > 0)
		{
			// data is less than root
			if (root.getLeft() != null)
			{
				return findParent(data, root.getLeft());
			}
		}
		
		return root;
	}
	
	private Node<T> findNode(T data, Node<T> parent)
	{	
		if (data == null || parent.getData().compareTo(data) < 0)
		{
			return parent.getRight();
		}
		else
		{
			return parent.getLeft();
		}
	}
	
	public Node<T> findCurrentParent(T data, Node<T> root)
	{
		// If there are no nodes, or root is the only node (which has no parent)
		if (root == null || root.children() == 0) return null;
		
		// If there is a right node, AND either both the data and the data in the node are null OR the data equals the data in the node, then root is the parent.
		if (root.getRight() != null && ((data == null && root.getRight().getData() == null) || root.getRight().getData().equals(data)))
		{
			return root;
		}
		else if (root.getLeft() != null && ((data == null && root.getLeft().getData() == null) || root.getLeft().getData().equals(data)))
		{
			return root;
		}
		else if (data == null || root.getData().compareTo(data) < 0)
		{
			return findCurrentParent(data, root.getRight());
		}
		else
		{
			return findCurrentParent(data, root.getLeft());
		}
	}
	
	/**
	 * Adds each data entry from the collection to this BST
	 * 
	 * @param c
	 */
	public void addAll(Collection<? extends T> c) throws NullPointerException {
		if (c == null) throw new NullPointerException();
		for (T element : c)
		{
			add(element);
		}
	}
	
	/**
	 * Removes a data entry from the BST
	 * 
	 * null is positive infinity
	 * 
	 * @param data The data entry to be removed
	 * @return The removed data entry (null if nothing is removed)
	 */
	public T remove(T data) {
		Node<T> parent = findCurrentParent(data, root);
		Node<T> node = findNode(data, parent);
		
		if (node == null) return null;
		
		Side side;
		
		// Determine if the node is to the parent's left or right
		if (node.getData() == null || parent.getData().compareTo(node.getData()) < 0)
		{
			side = Side.RIGHT;
		}
		else
		{
			side = Side.LEFT;
		}
		
		int children = node.children();
		
		switch(children)
		{
			case 0:
				if (side == Side.RIGHT)
				{
					parent.setRight(null);
				}
				else
				{
					parent.setLeft(null);
				}
				break;
			case 1:
				Node<T> child = node.getChild(node.getSide());
				if (side == Side.RIGHT)
				{
					parent.setRight(child);
				}
				else
				{
					parent.setLeft(child);
				}
				break;
		}
		return data;
	}
	
	/**
	 * Checks if the BST contains a data entry
	 * 
	 * null is positive infinity
	 * 
	 * @param data The data entry to be checked
	 * @return If the data entry is in the BST 
	 */
	public boolean contains(T data) {
		return false;
	}
	
	/**
	 * Finds the pre-order traversal of the BST
	 * 
	 * @return A list of the data set in the BST in pre-order
	 */
	public List<T> preOrder() {
		return null;
	}

	/**
	 * Finds the in-order traversal of the BST
	 * 
	 * @return A list of the data set in the BST in in-order
	 */
	public List<T> inOrder() {
		return null;
	}
	
	/**
	 * Finds the post-order traversal of the BST
	 * 
	 * @return A list of the data set in the BST in post-order
	 */
	public List<T> postOrder() {
		return null;
	}
	
	/**
	 * Checks to see if the BST is empty
	 * 
	 * @return If the BST is empty or not
	 */
	public boolean isEmpty() {
		return false;
	}
	
	/**
	 * Clears this BST
	 */
	public void clear() {
		
	}
	
	/**
	 * @return the size of this BST
	 */
	public int size() {
		return size;
	}
	
	/**
	 * First clears this BST, then reconstructs the BST that is
	 * uniquely defined by the given preorder and inorder traversals
	 * 
	 * (When you finish, this BST should produce the same preorder and
	 * inorder traversals as those given)
	 * 
	 * @param preorder a preorder traversal of the BST to reconstruct
	 * @param inorder an inorder traversal of the BST to reconstruct
	 */
	public void reconstruct(List<? extends T> preorder, List<? extends T> inorder) {
		
	}
	
	/*
	 * The following methods are for grading, do not modify them
	 */
	
	public Node<T> getRoot() {
		return root;
	}

	public void setRoot(Node<T> root) {
		this.root = root;
	}
	
	public void setSize(int size) {
		this.size = size;
	}

	public static class Node<K extends Comparable<K>> {
		
		private K data;
		private Node<K> left, right;
		
		// The side of the child. Only use if you are sure that there is only one child, otherwise it will be wrong.
		private Side side;
		
		public Node(K data) {
			setData(data);
		}

		public K getData() {
			return data;
		}

		public void setData(K data) {
			this.data = data;
		}
		
		public Node<K> getLeft() {
			return left;
		}
		
		public void setLeft(Node<K> left) {
			this.left = left;
			if (left != null) side = Side.LEFT;
		}
		
		public Node<K> getRight() {
			return right;
		}
		
		public void setRight(Node<K> right) {
			this.right = right;
			if (right != null) side = Side.LEFT;
		}
		
		public int children()
		{
			int c = 0;
			if (right != null)
			{
				c++;
			}
			if (right != null)
			{
				c++;
			}
			return c;
		}
		
		public Side getSide()
		{
			if (children() == 1)
			{
				return side;
			}
			else
			{
				return null;
			}
		}
		
		public Node<K> getChild(Side childSide)
		{
			if (childSide == Side.RIGHT)
			{
				return right;
			}
			else if (childSide == Side.LEFT)
			{
				return left;
			}
			return null;
		}
	}

}