#1 - Binary Tree Traversal

Pre-order:  7 1 0 2 3 3 8 7
In-order:   0 1 3 2 7 3 8 7
Post-order: 0 3 2 1 7 8 3 7 

#2 - Binary Search Tree

            Gorgonzola
      _____/          \____
     /                     \
 Blue                       Valdeon
    \                     /
     Cabrales          Stilton
          \           /
          Danablu  Roquefort   

#3 - Inheritance/Polymorphism

    compiler error
    John 1 Ringo 2
    Ringo 2
    George 2 
    Ringo 2
    John 2 
    Paul 3 George 2 
    compiler error
    runtime error 
    John 1 John 2 
    compiler error
    John 1 Ringo 2
    runtime error 
    Paul 3 George 2 
    George 2 

#4 - Recursive Backtracking

    public static void waysToClimbN(int stairs) {
        Stack<Integer> chosen = new Stack<Integer>();
        waysToClimbN(stairs, chosen);
    }

    private static void waysToClimbN(int stairs, Stack<Integer> chosen) {
        if (stairs == 0) {
            System.out.println(chosen);
        } else {
            for (int i = 1; i <= stairs; i++) {         
                chosen.push(i);                    
                waysToClimbN(stairs - i, chosen);    
                chosen.pop();                      
            } 
        }
    }

#5 - Collections Programming

    One possible solution

    public static void updateRegistration(Map<String, Set<String>> schedules, 
                                          Map<String, Map<String, String>> allUpdates) {
        for (String name : allUpdates.keySet()) {
            Map<String, String> personUpdates = allUpdates.get(name);
            for (String course : personUpdates.keySet()) {
                if (personUpdates.get(course).equals("add")) {
                    if (!schedules.containsKey(name)) {
                        schedules.put(name, new HashSet<String>());
                    }
                    schedules.get(name).add(course);
                } else {
                    schedules.get(name).remove(course); 
                }
            }
        }
    }

#6 - Comparable

    One possible solution

    public class Cookie implements Comparable<Cookie> {
        private int chips;
        private int raisins;
        
        public Cookie(int chips, int raisins) {
            if (chips < 0 || raisins < 0 || chips == 0 && raisins == 0) {
                throw new IllegalArgumentException();
            }
            this.chips = chips;
            this.raisins = raisins;
        }
        
        public String toString() {
            String result = "(";
            for (int i = 0; i < chips; i++) {
                result += "^";
            }
            for (int i = 0; i < raisins; i++) {
                result += "*";
            }
            return result + ")";
        }
        
        public int compareTo(Cookie other) {
            if (this.chips > 0 && other.chips == 0) {
                return -1;
            } else if (other.chips > 0 && this.chips == 0) {
                return 1;
            } else if (this.raisins > 0 && other.raisins == 0) {
                return 1;
            } else if (other.raisins > 0 && this.raisins == 0) {
                return -1;
            } else {
                return (this.chips + this.raisins) - (other.chips + other.raisins);
            }
        }
    }

#7 - Binary Trees

    One possible solution

    public void print() {
        print(overallRoot);
    }

    public void print(IntTreeNode root) {
        if (root == null) {
            System.out.print("empty");
        } else if (root.left == null && root.right == null) {
            System.out.print(root.data);
        } else {
            System.out.print("(");
            print(root.left);
            System.out.print(", " + root.data + ", ");
            print(root.right);
            System.out.print(")");
        }
    }

#8 - Binary Trees
    
    Two possible solutions

    // x = change(x) pattern only applying to the right side
    public void removeRightLeaves() {
        removeRightLeaves(overallRoot);
    }

    private IntTreeNode removeRightLeaves(IntTreeNode root) {
        if (root != null) {
            removeRightLeaves(root.left);
            root.right = removeRightLeaves(root.right);
            if (root.left == null && root.right == null) {
                root = null;
            }
        }
        return root;
    }

    // Look ahead for right leaves
    public void removeRightLeaves() {
        removeRightLeaves(overallRoot,);
    }

    private void removeRightLeaves(IntTreeNode root) {
        if (root != null) {
            removeRightLeaves(root.left);
            removeRightLeaves(root.right);
            if (root.right != null) {
                if (root.right.left == null && root.right.right == null) {
                    root.right = null;
                }
            }
        }
    }

#9 - LinkedIntList

    Two possible solutions

    // Remove the count nodes, and insert count – 1 new nodes into the
    // list, at the end of each run
    public void expand() {
        if (front != null) {
            int count = front.data;
            ListNode current = front.next;
            for (int i = 0; i < count - 1; i++) {
                current.next = new ListNode(current.data, current.next);
                current = current.next;
            }
            front = front.next; // remove count 
            // current guaranteed to not be null
            while (current.next != null) { // is there a pair in front of me?
                // current points to last expanded value
                count = current.next.data;
                current.next = current.next.next; // remove count
                current = current.next; // move current to the value
                for (int i = 0; i < count - 1; i++) {
                    current.next = new ListNode(current.data, current.next);
                    current = current.next;
                }
            }
        }
    }

    // Create a brand new list with the expanded values, set front to new list
    public void expand() {
        if (front != null) {
            ListNode newFront = null;
            int count = front.data;
            int value = front.next.data;
            newFront = new ListNode(value); // front case for the new list
            ListNode newListEnd = newFront;
            for (int i = 0; i < count - 1; i++) {
                newListEnd.next = new ListNode(value);
                newListEnd = newListEnd.next;
            }
            ListNode current = front.next.next;
            while (current != null) {
                count = current.data;
                value = current.next.data;
                for (int i = 0; i < count; i++) {
                    newListEnd.next = new ListNode(value);
                    newListEnd = newListEnd.next;
                }
                current = current.next.next;
            }
            front = newFront;
        }
    }