BSTree.java

/* *****************************************************************************
 *  Name:              Ada Lovelace
 *  Coursera User ID:  123456
 *  Last modified:     October 16, 1842
 **************************************************************************** */

public class BSTree<Key extends Comparable<Key>, Value> {
    private Node root = null;

    public class Node {
        private Key key;
        private Value val;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.val = value;
        }
    }

    public boolean isEmpty() {
        return (root == null);
    }

    public boolean comtains(Key key) {
        return (get(key) != null);
    }

    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    public Value get(Key key) {
        return get(root, key);
    }

    public Iterable<Key> keys() {
        Queue<Key> keyQueue = new Queue<Key>();
        inorder(root, keyQueue);
        return keyQueue;
    }

    private void inorder(Node node, Queue<Key> keyQueue) {
        if (node == null) return;
        inorder(node.left, keyQueue);
        keyQueue.enqueue(node.key);
        inorder(node.right, keyQueue);
    }

    private Value get(Node node, Key key) {
        if (node == null) return null;
        int cmp = key.compareTo(node.key);
        if (cmp > 0) return get(node.right, key);
        else if (cmp < 0) return get(node.left, key);
        else return node.val;
    }

    private Node put(Node node, Key key, Value value) {
        if (node == null) return new Node(key, value);
        int cmp = key.compareTo(node.key);
        if (cmp > 0) node.right = put(node.right, key, value);
        else if (cmp < 0) node.left = put(node.left, key, value);
        else node.val = value;
        return node;
    }

    public static void main(String[] args) {
        BSTree<String, Integer> bst = new BSTree<String, Integer>();
        while (!StdIn.isEmpty()) {
            String key = StdIn.readString();
            if (bst.comtains(key)) bst.put(key, bst.get(key) + 1);
            else bst.put(key, 1);
        }
        for (String s : bst.keys()) {
            System.out.printf("%d %s \n", bst.get(s), s);
        }
    }
}