1. Binary Tree Traversal Preorder : 4 1 0 3 9 2 7 8 Inorder : 1 3 0 4 7 2 9 8 Postorder: 3 0 1 7 2 8 9 4 2. Binary Search Trees +------------+ | Hilda | +------------+ / \ / \ / \ +------------+ +------------+ | David | | Johanna | +------------+ +------------+ / \ \ / \ \ / \ \ +------------+ +------------+ +------------+ | Alfur | | Frida | | Woodman | +------------+ +------------+ +------------+ / / / +------------+ | Twig | +------------+ 3. Inheritance / Polymorphism var1.method1(); Pet 1 / Doggo 3 /Pet 3 var2.method1(); Pet 1 / Pupper 3 var3.method1(); Pet 1 / Cat 3 var4.method1(); Pet 1 / Pupper 3 var5.method1(); Pet 1 / Pet 3 var6.method1(); Compiler Error var1.method2(); Compiler Error var2.method2(); Pupper 2 var3.method2(); Compiler Error var1.method3(); Doggo 3 / Pet 3 var2.method3(); Pupper 3 var3.method3(); Cat 3 ((Pupper) var6).method1(); Runtime Error ((Doggo) var3).method2(); Compiler Error ((Pupper) var4).method2(); Pupper 2 ((Pet) var3).method2(); Compiler Error ((Cat) var3).method2(); Cat 2 ((Pupper) var1).method1(); Runtime Error ((Doggo) var4).method3(); Pupper 3 ((Pet) var6).method3(); Doggo 3 / Pet 3 4. Comparable public class PokemonTrainer implements Comparable { private String name; private int badges; private int battlesWon; private int battlesTotal; public PokemonTrainer(String name, int badges) { this.name = name; this.badges = badges; } public int getBadges() { return badges; } public double getBattlePercent() { if (battlesTotal == 0) { return 0.0; } else { return 100.0 * battlesWon / battlesTotal; } } public void battle(boolean won) { battlesTotal++; if (won) { battlesWon++; } } public String toString() { String result = name + " has " + badges + " badge(s) and "; if (battlesTotal > 0) { result += "a " + ((int) getBattlePercent()) + "% win rate"; } else { result += "no battles"; } return result; } public int compareTo(PokemonTrainer other) { double diff = other.getBattlePercent() - this.getBattlePercent(); if (diff < 0) { return -1; } else if (diff > 0) { return 1; } else { diff = other.battlesTotal - this.battlesTotal; if (diff < 0) { return -1; } else if (diff > 0) { return 1; } else { return this.name.compareTo(other.name); } } } } 5. Collections public static Map numPlacesTraveled(List trips) { if (trips.isEmpty()) { throw new IllegalArgumentException(); } Map> traveled = new HashMap>(); for (String trip : trips) { int index = trip.indexOf(":"); String name = trip.substring(0, index); String location = trip.substring(index + 1, trip.length()); if (!traveled.containsKey(name)) { traveled.put(name, new HashSet()); } traveled.get(name).add(location); } Map counts = new HashMap(); for (String name : traveled.keySet()) { counts.put(name, traveled.get(name).size()); } return counts; } 6. Easier Binary Tree public boolean hasZeroPath() { if (overallRoot == null) { return true; } return hasZeroPath(overallRoot); } private boolean hasZeroPath(IntTreeNode node) { if(node == null) { return false; } else if(node.data != 0) { return false; } else if (node.left == null && node.right == null) { return true; } else { return hasZeroPath(node.left) || hasZeroPath(node.right); } } 7. Harder Binary Tree public void indicateMatching(IntTree other) { this.root = indicateMatching(this.overallRoot, other.overallRoot); } private IntTreeNode indicateMatching(IntTreeNode me, IntTreeNode them) { if (me == null && them == null) { return null; } else if (me == null) { IntTreeNode newMe = new IntTreeNode(-2); newMe.left = indicateMatching(null, them.left); newMe.right = indicateMatching(null, them.right); return newMe; } else if (them == null) { IntTreeNode newMe = new IntTreeNode(-1); newMe.left = indicateMatching(me.left, null); newMe.right = indicateMatching(me.right, null); return newMe; } else { me.left = indicateMatching(me.left, them.left); me.right = indicateMatching(me.right, them.right); return me; } } 8. LinkedIntList public void mergeFrom(LinkedIntList other) { if (other.front != null) { if (front == null) { front = other.front; } else { ListNode current1 = front; ListNode current2 = other.front; if (front.data <= other.front.data) { current1 = current1.next; } else { front = other.front; current2 = current2.next; } ListNode current3 = front; while (current1 != null && current2 != null) { if (current1.data <= current2.data) { current3.next = current1; current1 = current1.next; } else { current3.next = current2; current2 = current2.next; } current3 = current3.next; } if (current1 != null) { current3.next = current1; } else { current3.next = current2; } } other.front = null; } }