BinarySearchTree.java

import java.awt.*;
import java.util.*;

public class BinarySearchTree {
    private BinaryNode root;
    private ArrayList<BinaryNode> nodes = new ArrayList<>();

    public BinarySearchTree() {
        root = null;
    }

    public void add(BinaryNode x) {
        if (root == null) {
            root = x;
            return;
        }
        add(root, x);
    }

    private void add(BinaryNode parent, BinaryNode x) {
        if (parent == null) {
            return;
        }
        if (x.getValue() < parent.getValue()) {
            if (parent.getLeft() == null) {
                parent.setLeft(x);
            } else {
                add(parent.getLeft(), x);
            }
        } else {
            if (parent.getRight() == null) {
                parent.setRight(x);
            } else {
                add(parent.getRight(), x);
            }
        }
    }

    public BinaryNode remove(int target) {
        if (root == null) return null;
        BinaryNode temp = root;
        BinaryNode inorderSuccessor;
        if (root.getValue() == target) {
            if (root.getLeft() == null && root.getRight() == null) {
                root = null;
                return temp;
            } else if (root.getLeft() == null) {
                root = root.getRight();
                temp.setRight(null);
                return temp;
            } else if (root.getRight() == null) {
                root = root.getLeft();
                temp.setLeft(null);
                return temp;
            } else {
                inorderSuccessor = successor(root);
                swap(root, inorderSuccessor);
                if(root.getRight()==inorderSuccessor)
                {
                    root.setRight(inorderSuccessor.getRight());
                    inorderSuccessor.setRight(null);
                    return inorderSuccessor;
                }
                return remove(root.getRight(), target);
            }
        }
        return remove(root, target);
    }

    private BinaryNode successor(BinaryNode k) {
        BinaryNode temp = k;
        temp = temp.getRight();
        while (temp.getLeft() != null) {
            temp = temp.getLeft();
        }
        return temp;
    }

    private void swap(BinaryNode x, BinaryNode y) {
        int k = x.getValue();
        x.setValue(y.getValue());
        y.setValue(k);
    }

    private BinaryNode search(BinaryNode parent, int target)
    {
        if(parent == null) return null;
        if(parent.getLeft()!=null && parent.getLeft().getValue()==(target)||
                parent.getRight()!=null && parent.getRight().getValue()==(target))
            return parent;
        else if(target<parent.getValue())
            return search(parent.getLeft(),target);
        else
            return search(parent.getLeft(),target);
    }

    private BinaryNode remove(BinaryNode startNode, int target)
    {
        BinaryNode nodeToRemove, inorderSuccessor;
        BinaryNode parent = search(startNode,target);
        if(parent == null) return null;
        //decide if it is a left or right child
        boolean isLeft = parent.getLeft()!=null &&
                parent.getLeft().getValue()==(target);
        nodeToRemove = isLeft ? parent.getLeft() : parent.getRight();
        //degree 0
        if(nodeToRemove.getLeft() == null && nodeToRemove.getRight() == null)
        {
            if(isLeft)
                parent.setLeft(null);
            else
                parent.setRight(null);
            return nodeToRemove;
        }
        //degree 1
        else if(nodeToRemove.getLeft() == null)
        {
            if(isLeft)
                parent.setLeft(nodeToRemove.getRight());
            else
                parent.setRight(nodeToRemove.getRight());
            nodeToRemove.setRight(null);
            return nodeToRemove;
        }
        else if(nodeToRemove.getRight() == null)
        {
            if(isLeft)
                parent.setLeft(nodeToRemove.getLeft());
            else
                parent.setRight(nodeToRemove.getLeft());
            nodeToRemove.setLeft(null);
            return nodeToRemove;
        }
        //degree 2
        else
        {
            inorderSuccessor = successor(nodeToRemove);
            swap(inorderSuccessor, nodeToRemove);
            if(nodeToRemove.getRight()==inorderSuccessor)
            {
                nodeToRemove.setRight(inorderSuccessor.getLeft());
                inorderSuccessor.setRight(null);
                return inorderSuccessor;
            }
            return remove(nodeToRemove.getRight(), target);
        }
    }
    public String levelOrder()
    {
        String temp = "";
        Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
        queue.offer(root);
        while(!queue.isEmpty())
        {
            BinaryNode k = queue.poll();
            temp += k.getValue()+" ";
            if(k.getLeft()!=null)
                queue.offer(k.getLeft());
            if(k.getRight()!=null)
                queue.offer(k.getRight());
        }
        return temp.trim();
    }

    public ArrayList<BinaryNode> preOrder(){
    	nodes = new ArrayList<BinaryNode>();
    	preOrder(root, 1, 1);
    	return nodes;
    }
    private void preOrder(BinaryNode k, int pos, int height){
    	if(k == null) {
    		BinaryNode tempNode = new BinaryNode();
    		tempNode.setX(pos);
    		tempNode.setY(height);
    		nodes.add(tempNode);
    		return;
    	}
    	k.setX(pos);
    	k.setY(height);
    	nodes.add(k);
    	if(k != null)
    	{
    		// go left
    		preOrder(k.getLeft(), pos*2-1, height+1);
    		// go right
    		preOrder(k.getRight(), pos*2, height+1);
    	}
    }
    
    public int getHeight(){
    	return getHeight(root);
    }
    private int getHeight(BinaryNode k){
    	if(k == null) return -1;
    		return 1 + Math.max(getHeight(k.getLeft()), getHeight(k.getRight()));
    }
}