Problem #1, Inheritance and Polymorphism

solution
    var1.method2();                 error
    var2.method2();                 Carrot 2 / Turnip 3
    var3.method3();                 Parsnip 3
    var4.method1();                 Root 1 / Turnip 3       
    var2.method3();                 Turnip 3
    var6.method2();                 error
    var6.method3();                 Root 3
    ((Turnip)var6).method1();       error
    ((Carrot)var2).method1();       Root 1 / Turnip 3
    ((Parsnip)var2).method2();      error
    ((Turnip)var4).method3();       Turnip 3
    ((Root)var1).method1();         Root 1 / Root 3
    ((Root)var3).method1();         Parsnip 1
    ((Parsnip)var4).method2();      error
    ((Carrot)var4).method1();       error


Problem #2, Binary Trees

public void alternatesParity() {
	return alteratesParity(overallRoot);
}

private boolean alternatesParity(IntTreeNode root) {
	if (root == null) {
		return true;
	} else if (root.left == null && root.right == null) {
		return true;
	} else {
		boolean leftAlternates = alternatesParity(root.left);
		boolean rightAlternates = alternatesParity(root.right);
		if (root.left != null) {
			if (root.data % 2 != root.left.data % 2) {
				return leftAlternates && rightAlternates;
			} else {
				return false;
			}
		}	
		if (root.right != null) {
			if (root.data % 2 != root.right.data % 2) {
				return leftAlternates && rightAlternates;
			} else {
				return false;
			}
		}	
	}
}

Problem #3, LinkedIntList

public boolean bubble() {
    boolean swap = false;
    if (front != null && front.next != null) {
        if (front.data > front.next.data) {
            swap = true;
            ListNode temp = front;
            front = front.next;
            temp.next = front.next;
            front.next = temp;
        }
        ListNode current = front;
        while (current.next != null && current.next.next != null) {
            if (current.next.data > current.next.next.data) {
                swap = true;
                ListNode temp = current.next.next;
                current.next.next = temp.next;
                temp.next = current.next;
                current.next = temp;
            }
            current = current.next;
        }
    }
    return swap;
}

Problem #4, Binary Tree Traversal

pre:  8, 3, 2, 0, 4, 6, 9, 1, 7, 5
in:   0, 2, 3, 4, 6, 8, 1, 9, 5, 7
post: 0, 2, 6, 4, 3, 1, 5, 7, 9, 8

Problem #5, Binary Search Tree

                                   +------------+
                                   |  Pinch     |
                                   +------------+
                                /                  \
                             /                        \
                          /                              \
                  +-----------+                       +----------+
                  |   Edge    |                       |  Sloper  |
                  +-----------+                       +----------+
                /              \                     /		      \
               /                \                   / 		       \
              /                  \                 /			    \
    +-------------+          +-----------+    +-----------+     +------------+
    |     Chip    |          |    Jug    |    |   Pocket  |     | Undercling |
    +-------------+          +-----------+    +-----------+     +------------+
                   \                                    
                    \                                    
                     \                                    
                 +-------------+                     
                 |    Crimp    |                      
                 +-------------+  

Problem #6, Comparable


public class PokemonTrainer implements Comparable<PokemonTrainer> {
	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 {
			return other.battlesTotal – this.battlesTotal;
		}
	}
}

Problem #7, Collections Programming

public static double recordScore(Map<String, List<Integer>> scores, String name, int score) {
	if (score < 0 || score > 30) {
		throw new IllegalArgumentException();
	}
	if (!scores.containsKey(name)) {
		scores.put(name, new LinkedList<Integer>());
	}
	scores.get(name).add(0, score);
	int total = 0;
	for (int i : scores.get(name)) {
		total += i;
	}
	return (int) Math.round((1000.0) * total / (scores.get(name).size() * 30)) / 10.0;
}

Problem #8, Binary Trees


public void limitLeaves(int min) {
    overallRoot = limitLeaves(overallRoot, min);
}

private IntTreeNode limitLeaves(IntTreeNode root, int min) {
    if (root != null) {
        root.left = limitLeaves(root.left, min);
        root.right = limitLeaves(root.right, min);
        if (root.left == null && root.right == null && root.data <= min)
            root = null;
    }
    return root;
}