BinarySearchTreeString.java

public class BinarySearchTreeString {
    NodeString root;

    public BinarySearchTreeString() {
        root = null;
    }

    public void insert(String key) {
        root = insertRec(root, key);
    }

    private NodeString insertRec(NodeString root, String key) {
        if (root == null) {
            root = new NodeString(key);
            return root;
        }
        if (key.compareTo(key) < root.key.compareTo(key)) {
            root.left = insertRec(root.left, key);
        } else if (key.compareTo(key) > root.key.compareTo(key)) {
            root.right = insertRec(root.right, key);
        }

        return root;
    }

    public void printPreorder(NodeString node) {
        if (node == null) {
            return;
        }
        System.out.print(node.key + " ");
        printPreorder(node.left);
        printPreorder(node.right);
    }

    public void printInorder(NodeString node) {
        if (node == null) {
            return;
        }
        printInorder(node.left);
        System.out.print(node.key + " ");
        printInorder(node.right);
    }

    public void printPostorder(NodeString node) {
        if (node == null) {
            return;
        }
        printPostorder(node.left);
        printPostorder(node.right);
        System.out.print(node.key + " ");
    }

    public void printPreorder() {
        printPreorder(root);
    }

    public void printInorder() {
        printInorder(root);
    }

    public void printPostorder() {
        printPostorder(root);
    }

    public void deleteKey(String key) {
        root = deleteRec(root, key);
    }

    public NodeString deleteRec(NodeString root, String key) {
        if (root == null) {
            return root;
        }

        if (key.compareTo(key) < root.key.compareTo(key)) {
            root.left = deleteRec(root.left, key);
        } else if (key.compareTo(key) > root.key.compareTo(key)) {
            root.right = deleteRec(root.right, key);
        } else {

            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            root.key = minValue(root.right);
            root.right = deleteRec(root.right, root.key);
        }

        return root;
    }

    String minValue(NodeString root) {
        String minv = root.key;
        while (root.left != null) {
            minv = root.left.key;
            root = root.left;
        }
        return minv;
    }
   
    private int countNodes(NodeString n) {
        if (n == null) {
            return 0;
        } else {
            return 1 + countNodes(n.left) + countNodes(n.right);
        }
    }

    public int size() {
        return countNodes(root);
    }
}