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 Tree Search

																	 +------------+
                                   |  Ravioli   |
                                   +------------+
                                /                  \
                             /                        \
                 +------------+                      +------------+
                 | Maccheroni |                      |    Ziti    |
                 +------------+                      +------------+
                /              \                    /
               /                \                  /
        +------------+    +------------+    +------------+
        | Conchiglie |    |   Penne    |    |  Rigatoni  |
        +------------+    +------------+    +------------+
                                                          \
                                                           \
                                                    +------------+
                                                    | Tortellini |
                                                    +------------+

3) Inheritance / Polymorphism

 Statement                  | Output
----------------------------|-------------------------------
 var1.method1();            | Coffee 1 / Drip  2
 var2.method1();            | Latte  1 / Mocha 1
 var3.method1();            | Coffee 1 / Drip  2
 var4.method1();            | Latte  1
 var5.method1();            | Latte  1 / Mocha 1
 var6.method1();            | compiler error
 var1.method2();            | Drip   2
 var2.method2();            | Latte  2 / Latte 1 / Mocha 1
 var3.method2();            | Drip   2
 var4.method2();            | Latte  2 / Latte 1
 var5.method2();            | Latte  2 / Latte 1 / Mocha 1
 var6.method2();            | compiler error
 var3.method3();            | Drip   3
 var5.method3();            | compiler error
 ((Drip)var1).method3();    | Drip   3
 ((Mocha)var5).method3();   | Mocha  3
 ((Coffee)var3).method3();  | compiler error
 ((Drip)var2).method3();    | runtime error
 ((Latte)var2).method2();   | Latte  2 / Latte 1 / Mocha 1
 ((Mocha)var6).method2();   | runtime error

4) Comparable

One possible solution is shown below

public class MovieRating implements Comparable<MovieRating> {
    private String name;
    private int[] ratings;
    private int numRatings;

    public MovieRating(String name) {
        ratings = new int[6];
        this.name = name;
        numRatings = 0;
    }

    public void addRating(int n) {
        ratings[n]++;
        numRatings++;
    }

    public int getVotes(int n) {
        return ratings[n];
    }

    public double averageRating() {
        if (numRatings == 0) {
            return 0.0;
        } else {
            int totalRating = 0;
            for (int i = 1; i <= 5; i++) {
                totalRating += ratings[i] * i;
            }
            return ((double) totalRating) / numRatings;
        }
    }

    public String toString() {
        if (numRatings == 0) {
            return name + ": No ratings yet!";
        } else {
            return name + ": " + averageRating() + " (" + numRatings + " ratings)";
        }
    }

    public int compareTo(MovieRating other) {
        if (this.averageRating() < other.averageRating()) {
            return -1;
        } else if (this.averageRating() > other.averageRating()) {
            return 1;
        } else {
            for (int i = 5; i >= 0; i--) {
                int diff = ratings[i] - other.ratings[i];
                if (diff != 0) {
                    return diff;
                }
            }
            return other.name.compareTo(this.name);
        }
    }
}

5) Collections Programming

One possible solution is shown below

public static Map<String, Set<String>> twoFlightsAway(Map<String, Set<String>> flights) {
    Map<String, Set<String>> result = new TreeMap<String, Set<String>>();
    for (String start : flights.keySet()) {
        Set<String> twoAway = new TreeSet<String>();
        Set<String> destinations = flights.get(start);
        for (String dest : destinations) {
            for (String destFromDest : flights.get(dest)) {
                if (!destFromDest.equals(start) && !destinations.contains(destFromDest)) {
                    twoAway.add(destFromDest);
                }
            }
        }
        if (!twoAway.isEmpty()) {
            result.put(start, twoAway);
        }
    }
    return result;
}

6) Binary Tree Programming I

One possible solution is shown below

public int randomPathSum() {
	return randomPathSum(overallRoot, new Random());
}

private int randomPathSum(IntTreeNode root, Random r) {
    // Another solution: int num = (int) (Math.random() * 3);
	int num = r.nextInt(3);
	if (root == null || num == 0) {
		return 0;
	} else if (num == 1) {
		return root.data + randomPathSum(root.left, r);
	} else {
		return root.data + randomPathSum(root.right, r);
	}
}

7) Binary Tree Programming II

One possible solution is shown below

public void makeFull() {
    overallRoot = makeFull(overallRoot, 1);
}

private IntTreeNode makeFull(IntTreeNode root, int level) {
    if (root != null) {
        if (root.left == null && root.right != null) {
            root = new IntTreeNode(-level, root, root.right);
            root.left.right = null;
        } else if (root.left != null && root.right == null) {
            root = new IntTreeNode(-level, root.left, root);
            root.right.left = null;
        }
        root.left = makeFull(root.left, level + 1);
        root.right = makeFull(root.right, level + 1);
    }
    return root;
}

8) LinkedList Programming

One possible solution is shown below

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 node 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;
            }
        }
    }
}