1. Binary Tree Traversal Preorder : 4 1 0 2 9 3 8 5 Inorder : 0 1 9 2 4 3 8 5 Postorder: 0 9 2 1 5 8 3 4 2. Binary Search Trees +-------------+ | Jughead | +-------------+ / \ / \ +-------------+ +-------------+ | Cheryl | | Pop | +-------------+ +-------------+ / / \ / / \ +-------------+ +-------------+ +-------------+ | Archie | | Kevin | | Veronica | +-------------+ +-------------+ +-------------+ \ \ +-------------+ | Betty | +-------------+ 3. Inheritance / Polymorphism Call | Output --------------------------------|-------------------------- var1.method1(); | Shape 1 / Rectangle 3 /Shape 3 var2.method1(); | Shape 1 / Square 3 var3.method1(); | Shape 1 / Circle 3 var4.method1(); | Shape 1 / Square 3 var5.method1(); | Shape 1 / Shape 3 var6.method1(); | Compiler Error var1.method2(); | Compiler Error var2.method2(); | Square 2 var3.method2(); | Compiler Error var1.method3(); | Rectangle 3 / Shape 3 var2.method3(); | Square 3 var3.method3(); | Circle 3 ((Square) var6).method1(); | Runtime Error ((Rectangle) var3).method2(); | Compiler Error ((Square) var4).method2(); | Square 2 ((Shape) var3).method2(); | Compiler Error ((Circle) var3).method2(); | Circle 2 ((Square) var1).method1(); | Runtime Error ((Rectangle) var4).method3(); | Square 3 ((Shape) var6).method3(); | Rectangle 3 / Shape 3 4. Comparable: One possible solution is shown public class IceCream implements Comparable { private int totalScoops; private boolean hasSprinkles; private Map scoops; public IceCreame() { scoops = new HashMap<>(); } public void add(String flavor, int n) { if (n < 1) { throw new IllegalArgumentException(); } if (scoops.containsKey(flavor)) { scoops.put(flavor, scoopts.get(flavor) + n) } else { scoops.put(flavor, n); } totalScoops += n; } public void addSprinkles() { hasSprinkles = true; } public int get(String flavor) { if (scoops.containsKey(flavor)) { return scoops.get(flavor); } else { return 0; } } public String toString() { if (totalScoops == 0) { return "No ice cream :("; } else { return totalScoops + " scoops of ice of ice cream with " + scoops.keySet(); } } public int compareTo(IceCream other) { if (this.totalScoops != other.totalScoops) { return this.totalScoops - other.totalScoops; } else if (this.scoops.size() != other.scoops.size()) { return other.scoops.size() - this.scoops.size(); } else { if (this.hasSprinkles && !other.hasSprinkles) { return 1; } else if (!this.hasSprinkles && other.hasSprinkles) { return -1; } else { return 0; } } } } 5. Collections: One possible solution is shown public Map> favoriteFoods(Map> ratings, double target) { Map> result = new TreeMap<>(); for (String person : ratings.keySet()) { result.put(person, new TreeSet<>()); Map ratingsFor = ratings.get(person); for (String food : ratingsFor.keySet()) { if (ratingsFor.get(food) >= target) { result.get(person).add(food); } } } return result; } 6. Easier Binary Tree: One possible solution is shown public int countMatching() { return countMatching(this.overallRoot); } private int countMatching(IntTreeNode root) { if (root == null) { return 0; } else if (root.left != null && root.right != null && root.left.data % 2 == root.right.data % 2) { return 1 + countMatching(root.left) + countMatching(root.right); } else { return countMatching(root.left) + countMatching(root.right); } } 7. Harder Binary Tree: One possible solution is shown public void trimTo(int level) { if (level < 1) { throw new IllegalArgumentException(); } overallRoot = trimTo(overallRoot, 1, level); } private IntTreeNode trimTo(IntTreeNode root, int curr, int level) { if (curr <= level) { if (root == null) { return null; } else if (root.left == null && root.right == null) { return null; } else { root.left = trimTo(root.left, curr + 1, level); root.right = trimTo(root.right, curr + 1, level); return root; } } return root; } 8. LinkedIntList: One possible solution is shown public LinkedIntList removeAlternating() { LinkedIntList list = new LinkedIntList(); if (front != null && front.next != null) { list.front = front; front = front.next; ListNode curr = front; ListNode curr2 = list.front; curr2.next = null; int count = 1; while (curr != null && curr.next != null && curr.next.next != null) { if (count % 2 == 0) { curr2.next = curr.next; curr.next = curr.next.next; } else { curr2.next = curr.next.next; curr.next.next = curr.next.next.next; } count++; curr = curr.next; curr2 = curr2.next; curr2.next = null; } } return list; }