Practice Exercise 3.2.A

BinaryTree.java

import java.util.Optional;

public interface BinaryTree<K,V> {
    void put(K key,V value);

    Optional<V> get(K key);
}

BinaryTreeNode.java

import java.util.Optional;

public class BinaryTreeNode<K,V> {
    private BinaryTreeNode<K,V> left;
    private BinaryTreeNode<K,V> right;
    private K key;
    private V value;

    public BinaryTreeNode(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public Optional<BinaryTreeNode<K,V>> getLeft() {
        return Optional.ofNullable(left);
    }

    public Optional<BinaryTreeNode<K,V>> getRight() {
        return Optional.ofNullable(right);
    }

    public void setLeft(BinaryTreeNode<K,V> left) {
        this.left = left;
    }

    public void setRight(BinaryTreeNode<K,V> right) {
        this.right = right;
    }

    public K getKey() {
        return key;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }
}

SimpleBinaryTree.java

import java.util.LinkedList;
import java.util.Optional;
import java.util.Queue;

public class SimpleBinaryTree<K, V> implements BinaryTree<K, V> {
    protected BinaryTreeNode<K, V> root;

    public void put(K key, V value) {
        if (root == null)
            root = new BinaryTreeNode<>(key, value);
        else
            put(key, value, root);
    }

    private void put(K key, V value, BinaryTreeNode<K, V> node) {
        if (((Comparable) key).compareTo(node.getKey()) == 0) {
            node.setKey(key);
            node.setValue(value);
        } else if (((Comparable) key).compareTo(node.getKey()) < 0) {
            if (node.getLeft().isPresent())
                put(key, value, node.getLeft().get());
            else
                node.setLeft(new BinaryTreeNode<>(key, value));
        } else {
            if (node.getRight().isPresent())
                put(key, value, node.getRight().get());
            else
                node.setRight(new BinaryTreeNode<>(key, value));
        }
    }

    public Optional<V> get(K key) {
        return Optional.ofNullable(root).flatMap(n -> get(key, n));
    }

    private Optional<V> get(K key, BinaryTreeNode<K, V> node) {
        if (((Comparable) key).compareTo(node.getKey()) == 0)
            return Optional.of(node.getValue());
        else if (((Comparable) key).compareTo(node.getKey()) < 0)
            return node.getLeft().flatMap(n -> get(key, n));
        else
            return node.getRight().flatMap(n -> get(key, n));
    }

    public void leftRotate(BinaryTreeNode<K, V> nodeX,
                           BinaryTreeNode<K, V> parent) {
        BinaryTreeNode<K, V> nodeY = nodeX.getRight().get();
        nodeX.setRight(nodeY.getLeft().orElse(null));
        if (parent == null)
            this.root = nodeY;
        else if (parent.getLeft().filter(n -> n == nodeX).isPresent())
            parent.setLeft(nodeY);
        else
            parent.setRight(nodeY);
        nodeY.setLeft(nodeX);
    }

    public void rightRotate(BinaryTreeNode<K, V> nodeX,
                           BinaryTreeNode<K, V> parent) {
       // Write your code here
    }


    public Optional<K> minKey() {
        return Optional.ofNullable(root).map(this::minKey);
    }

    protected K minKey(BinaryTreeNode<K, V> node) {
        return node.getLeft().map(this::minKey).orElse(node.getKey());
    }

    public void printBfs() {
        Optional.ofNullable(root).ifPresent(r -> {
            Queue<BinaryTreeNode<K, V>> queue = new LinkedList<>();
            queue.add(r);
            while (!queue.isEmpty()) {
                BinaryTreeNode<K, V> node = queue.remove();
                System.out.println(node.getKey());
                node.getLeft().ifPresent(queue::add);
                node.getRight().ifPresent(queue::add);
            }
        });
    }


    public void printDfs() {
        Optional.ofNullable(root).ifPresent(this::printDfs);
    }

    private void printDfs(BinaryTreeNode<K, V> node) {
        //System.out.println("PREORDER " + node.getKey());
        node.getLeft().ifPresent(this::printDfs);
        System.out.println("INORDER " + node.getKey());
        node.getRight().ifPresent(this::printDfs);
        //System.out.println("POSTORDER " + node.getKey());
    }


    public static void main(String[] args) {
        SimpleBinaryTree<Integer, String> binaryTree = new SimpleBinaryTree<Integer, String>();
        System.out.println(binaryTree.minKey());
        binaryTree.put(457998224, "Isabel");
        binaryTree.put(366112467, "John");
        binaryTree.put(671031776, "Ruth");
        binaryTree.put(225198452, "Sarah");
        binaryTree.put(419274013, "Peter");
        binaryTree.put(751965387, "Tom");

        System.out.println(binaryTree.get(457998224));
        System.out.println(binaryTree.get(366112467));
        System.out.println(binaryTree.get(671031776));
        System.out.println(binaryTree.get(225198452));
        System.out.println(binaryTree.get(419274013));
        System.out.println(binaryTree.get(751965387));

        binaryTree.put(751965387, "Sam");

        System.out.println(binaryTree.get(751965387));
        System.out.println(binaryTree.get(999999999));
        System.out.println(binaryTree.minKey());

        binaryTree.printDfs();
        binaryTree.printBfs();
    }
}