CS132 Quiz 4 Worksheet Revised

import java.util.ArrayList;
import java.util.TreeMap;

public class Quiz_4<K extends Comparable<K>, V> {
    private class Node {
        private K key;
        private V data;
        private Node left, right;

        public Node(K key, V data) {
            this.key = key;
            this.data = data;
        }
    }

    private Node root;

    public Quiz_4() {
        root = null;
    }

    public void add(K key, V data) {
        addAux(key, data, root);
    }

    public Quiz_4<K,V> addAux(K key, V data, Node tree) {
        if (tree == null) {
            tree = new Node(key, data);
            return this;
        }
        if (key.compareTo(tree.key) == 0) {
            tree.data = data;
            return this;
        }
        if (key.compareTo(root.key) < 0) {
            addAux(key, data, tree.left);
            return this;
        }
        addAux(key, data, tree.right);
        return this;
    }

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

    public int sizeAux(Node tree) {
        return tree == null ? 0 : 1 + sizeAux(tree.right) + sizeAux(tree.left);
    }

    public V maxNonRec() {
        if (root == null) {
            return null;
        }
        Node n = root;
        while (n.right != null) {
            n = n.right;
        }
        return n.data;
    }

    public V max() {
        return root == null ? null : maxAux(root);
    }

    public V maxAux(Node tree) {
        return tree.right == null ? tree.data : maxAux(tree.right);
    }

    public V min() {
        return root == null ? null : minAux(root);
    }

    public V minAux(Node tree) {
        return tree.left == null ? tree.data : minAux(tree.left);
    }

    public String postOrderTraversal() {
        return postAux(root);
    }

    public String postAux(Node tree) {
        return tree == null ? "" : postAux(tree.left) + postAux(tree.right) + tree.key;
    }

    public int getNumInteriorNodes() {
        return interiorAux(root);
    }

    public int interiorAux(Node tree) {
        return tree.right == null && tree.left == null ? 0 : 1 + interiorAux(tree.right) + interiorAux(tree.left);
    }

    public int getHeight() {
        return heightAux(root);
    }

    public int heightAux(Node tree) {
        return tree == null ? 0 : 1 + Math.max(heightAux(tree.left), heightAux(tree.right));
    }

    public void leaves(ArrayList<K> L) {
        L = leavesAux(root, L);
    }

    public ArrayList<K> leavesAux(Node tree, ArrayList<K> list) {
        if (tree.left != null || tree.right != null) {
            list = leavesAux(tree.left, list);
            list = leavesAux(tree.right, list);
        }
        list.add(tree.key);
        return list;
    }

    public ArrayList<V> getDecreasingOrderList() {
        ArrayList<V> list = new ArrayList<V>();
        return decreasingListAux(root, list);
    }

    public ArrayList<V> decreasingListAux(Node tree, ArrayList<V> list) {
        if (tree == null) {
            return list;
        }
        list = decreasingListAux(tree.right, list);
        list.add(tree.data);
        list = decreasingListAux(tree.left, list);
        return list;
    }

    public void getDataOneChildNodes(ArrayList<V> L) {
        L = oneChildPolicy(root, L);
    }

    public ArrayList<V> oneChildPolicy(Node tree, ArrayList<V> L) {
        if (tree != null) {
            if (tree.left == null ^ tree.right == null) {
                L.add(tree.data);
            }
            L = oneChildPolicy(tree.left, L);
            L = oneChildPolicy(tree.right, L);
        }
        return L;
    }

    public ArrayList<K> getKeyNodesAtLevel(int targetLevel) {
        ArrayList<K> list = new ArrayList<K>();
        return nodesAtLevelAux(targetLevel, root, list);
    }

    public ArrayList<K> nodesAtLevelAux(int level, Node tree, ArrayList<K> list) {
        if (tree == null) {
            return list;
        }
        if(level == 1) {
            list.add(tree.key);
            return list;
        }
        list = nodesAtLevelAux(level-1, tree.right, list);
        list = nodesAtLevelAux(level-1, tree.left, list);
        return list;
    }
    public TreeMap<K,V> placeKeysValues() {
        TreeMap<K,V> map = new TreeMap<K,V>();
        return placeKeysValuesAux(root, map);
    }
    public TreeMap<K,V> placeKeysValuesAux(Node tree, TreeMap<K,V> map) {
        if(tree == null) {
            return map;
        }
        map = placeKeysValuesAux(tree.left, map);
        map.put(tree.key,tree.data);
        map = placeKeysValuesAux(tree.right, map);
        return map;
    }
}