BinarySearchTree.java

package datastructs;public class BinarySearchTree<K extends Comparable<K>, U> {    private TreeNode<K, U> root;    private TreeNode<K, U> currentNode;    private U outputValue;    private K outputKey;    public BinarySearchTree() {        root = null;    }    public void add(K key, U value){        if(root != null){            addNode(root, key, value);        }else{            root = new TreeNode<K, U>(key, value, null, null);        }    }    private void addNode(TreeNode<K, U> node, K key, U value){        if(node != null){            if(key.compareTo(node.getKey()) >= 0){                if(node.getRightChild() != null){                    addNode(node.getRightChild(), key, value);                }else{                    node.setRightChild(new TreeNode(key, value, null, null));                }            }else{                if(node.getLeftChild() != null){                    addNode(node.getLeftChild(), key, value);                }else{                    node.setLeftChild(new TreeNode(key, value, null, null));                }            }        }    }    public void removeKey(K key){        TreeNode<K, U> firstNode = root, secondNode = null;        while(firstNode != null){            int temp = key.compareTo(firstNode.getKey());            if(temp == 0){                break;            }else{                secondNode = firstNode;                if(temp < 0){                    firstNode = firstNode.getLeftChild();                }else{                    firstNode = firstNode.getRightChild();                }            }        }        if(firstNode == null) return;        if(firstNode.getRightChild() == null){            if(secondNode == null){                root = firstNode.getLeftChild();            }else{                if(firstNode == secondNode.getLeftChild()){                    secondNode.setLeftChild(firstNode.getLeftChild());                }else{                    secondNode.setRightChild(firstNode.getRightChild());                }            }        }else{            TreeNode<K, U> leftMost = firstNode.getRightChild();            secondNode = null;            while(leftMost.getLeftChild() != null){                secondNode = leftMost;                leftMost = leftMost.getLeftChild();            }            if(secondNode != null){                secondNode.setLeftChild(leftMost.getRightChild());            }else{                firstNode.setRightChild(leftMost.getRightChild());            }            firstNode.setKey(leftMost.getKey());            firstNode.setData(leftMost.getData());        }    }    public void removeValue(U value){        removeKey(searchByValue(value));    }    public U searchByKey(K key){        searchNodeByKey(root, key);        return outputValue;    }    private void searchNodeByKey(TreeNode<K, U> node, K key){        if(node != null){            searchNodeByKey(node.getLeftChild(), key);            searchNodeByKey(node.getRightChild(), key);            if(node.getKey().equals(key)){                outputValue = node.getData();            }        }    }        public K searchByValue(U value){        searchNodeByValue(root, value);        return outputKey;    }    private void searchNodeByValue(TreeNode<K, U> node, U value){        if(node != null){            searchNodeByValue(node.getLeftChild(), value);            searchNodeByValue(node.getRightChild(), value);            if(node.getData().equals(value)){                outputKey = node.getKey();            }        }    }    public String printTreeData(){        StringBuilder sb = new StringBuilder();        printNode(root, sb);        return sb.toString();    }    private void printNode(TreeNode<K, U> node, StringBuilder sb){        if(node != null){            sb.append("Key: ");            sb.append(node.getKey());            sb.append("  Value: ");            sb.append(node.getData());            sb.append("\n");            printNode(node.getLeftChild(), sb);            printNode(node.getRightChild(), sb);        }    }}