problem #1

        Preorder traversal  6, 7, 1, 9, 4, 8, 2, 3, 5, 0
        Inorder traversal   9, 1, 4, 7, 6, 3, 2, 5, 8, 0
        Postorder traversal 9, 4, 1, 7, 3, 5, 2, 0, 8, 6

problem #2

                                   +------------+
                                   |    Mark    |
                                   +------------+
                                /                  \
                             /                        \
                          /                              \
                 +------------+                      +------------+
                 |   Denny    |                      |   Steven   |
                 +------------+                      +------------+
                /              \                    /
               /                \                  /
              /                  \                /
        +------------+    +------------+    +------------+
        | Claudette  |    |    Lisa    |    |    Peter   |
        +------------+    +------------+    +------------+
                         /
                        /
                       /
                +------------+
                |   Johnny   |
                +------------+

problem #3

solutions

    public Set<Point> removeDuplicates(List<Point> list) {
        Set<Point> result = new HashSet<Point>();
        Iterator<Point> itr = list.iterator();
        while (itr.hasNext()) {
            Point p = itr.next();
            if (result.contains(p)) {
                itr.remove();
            } else {
                result.add(p);
            }
        }
        return result;
    }

    public Set<Point> removeDuplicates(List<Point> list) {
        Set<Point> result = new HashSet<Point>();
        for (int i = 0; i < list.size(); i++) {
            if (result.contains(list.get(i))) {
                list.remove(i);
                i--;
            }
            result.add(list.get(i));
        }
        return result;
    }

problem #4
       
    public class Movie implements Comparable<Movie> {
        private String title;
        private String director;
        private int reviews;
        private double total;
        private double maxRating;
        private String maxComment;
    
        public Movie(String title, String director) {
            this.title = title;
            this.director = director;
            this.reviews = 0;
            this.total = 0.0;
        }
    
        public void review(double rating, String comment) {
            reviews++;
            total += rating;
            if (rating > maxRating) {
              maxRating = rating;
              maxComment = comment;
            }
        }
    
        public String getTitle() {
            return title;
        }
    
        public double getRating() {
            if (reviews == 0)
                return 0.0;
            else
                return total / reviews;
        }
    
        public String toString() {
            double rating = (int) (10.0 * getRating()) / 10.0;
            String result = title + ", by " + director + ", " + rating + " '"
                + maxComment + "'";
            return result;
        }
    
        public int compareTo(Movie other) {
            double delta = other.getRating() - getRating();
            if (delta < 0)
                return -1;
            else if (delta > 0)
                return 1;
            else // delta == 0
                return other.reviews - reviews;
        }
    }

problem #5

    public boolean hasPathSum(int sum) {
        return hasPathSum(overallRoot, sum);
    }

    private boolean hasPathSum(IntTreeNode root, int sum) {
        if (root == null)
            return false;
        if (root.data == sum)
            return true;
        int sum2 = sum - root.data;
        return hasPathSum(root.left, sum2) || hasPathSum(root.right, sum2);
    }

problem #6

      map1: {bar=1, baz=2, foo=3, mumble=4}
      map2: {1=earth, 2=wind, 3=air, 4=fire}
      map returned: {bar=earth, baz=wind, foo=air, mumble=fire}

      map1: {five=105, four=104, one=101, six=106, three=103, two=102}
      map2: {99=uno, 101=dos, 103=tres, 105=quatro}
      map returned: {five=quatro, one=dos, three=tres}

      map1: {a=42, b=9, c=7, d=15, e=11, f=24, g=7}
      map2: {1=four, 3=score, 5=and, 7=seven, 9=years, 11=ago}
      map returned: {b=years, c=seven, e=ago, g=seven}

Problem #7

        Statement                       Output
        ------------------------------------------------------------
        var1.method1();                 Soap 1/Dish 3/Soap 3
        var2.method1();                 Soap 1/Fork 3
        var3.method1();                 Soap 1/Bowl 3
        var4.method1();                 Soap 1/Fork 3
        var5.method1();                 Soap 1/Soap 3
        var6.method1();                 compiler error
        var1.method2();                 compiler error
        var2.method2();                 Fork 2
        var3.method2();                 compiler error
        var1.method3();                 Dish 3/Soap 3
        var2.method3();                 Fork 3
        var3.method3();                 Bowl 3
        ((Fork)var6).method1();         runtime error
        ((Dish)var3).method2();         compiler error
        ((Fork)var4).method2();         Fork 2
        ((Soap)var3).method2();         compiler error
        ((Bowl)var3).method2();         Bowl 2
        ((Fork)var1).method1();         runtime error
        ((Dish)var4).method3();         Fork 3
        ((Soap)var6).method3();         Dish 3/Soap 3


Problem #8

    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;
    }

problem #9

    public void weave(LinkedIntList other) {
        if (front == null) {
            front = other.front;
            other.front = null;
        } else if (other.front != null) {
            ListNode current1 = front;
            ListNode current2 = other.front;
            while (current1.next != null && current2.next != null) {
                ListNode temp = current1.next;
                current1.next = current2;
                current2 = current2.next;
                current1.next.next = temp;
                current1 = temp;
            }
            if (current1.next == null)
                current1.next = current2;
            else {
                current2.next = current1.next;
                current1.next = current2;
            }
            other.front = null;
        }
    }