Key to CSE143 Midterm, Summer 2018

1. 

Pre-order: 2, 4, 6, 3, 1, 5, 9, 8, 7, 0
In-order: 3, 6, 4, 9, 5, 1, 8, 2, 0, 7
Post-order: 3, 6, 9, 5, 8, 1, 4, 0, 7, 2

2.

                       +----------------+
                       |   Clementine   |
                       +----------------+
                    /                  \
                 /                        \
              /                              \
     +-------------+                      +------------+
     |  Charlotte  |                      |    Lee     |
     +-------------+                      +------------+
                                        /              \
                                       /                \
                                      /                  \
                               +--------------+      +------------+
                               |   Dolores    |      |    Maeve   |
                               +--------------+      +------------+
                                             \                   \
                                              \                   \
                                               \                   \
                                         +------------+      +------------+
                                         |    Elsie   |      |    Teddy   |
                                         +------------+      +------------+

3. One possible solution appears below.

    public Set<String> intersectingHobbies(String hobby, Map<String, Set<String>> hobbies) {
        Set<String> courses = new TreeSet<String>();
        for (String name : hobbies.keySet()) {
            Set<String> namesCourses = hobbies.get(name);
            if (namesCourses.contains(hobby)) {
                for (String course : namesCourses) {
                    courses.add(course);
                }
            }
        }
        return courses;
    }

4. One possible solution appears below.

public class CoffeeDrink implements Comparable<CoffeeDrink> {
  private Set<String> addins;
  private double ounces;
  private int caffeineMg;

  public CoffeeDrink(double ounces, int caffeineMg) {
    if (ounces < 0 || caffeineMg < 0) {
      throw new IllegalArgumentException("ounces and caffeineMg must be non-negative");
    }
    this.addins = new HashSet<String>();
    this.ounces = ounces;
    this.caffeineMg = caffeineMg;
  }

  public void add(String addin, double ounces, int caffeineMg) {
    if (ounces < 0 || caffeineMg < 0) {
      throw new IllegalArgumentException("ounces and caffeineMg must be non-negative");
    }
    this.ounces += ounces;
    this.caffeineMg += caffeineMg;
    this.addins.add(addin);
  }

  public boolean hasAddin(String addin) {
    for (String s : this.addins) {
      if (addin.equalsIgnoreCase(s)) {
        return true;
      }
    }
    return false;
  }

  public String toString() {
    String result = this.ounces + "oz coffee ";
    if (!this.addins.isEmpty()) {
      result += "with " + addins.toString() + " ";
    }
    return result + "(" + caffeineMg + "mg caffeine)";
  }

  public boolean isCaffeinated() {
    return this.caffeineMg >= 10;
  }
  
  public int compareTo(CoffeeDrink other) {
    if (this.caffeineMg != other.caffeineMg) {
      return this.caffeineMg - other.caffeineMg;
    } else if (this.ounces < other.ounces) {
      return -1;
    } else if (this.ounces > other.ounces) {
      return 1;
    } else {
      return other.addins.size() - this.addins.size();
    }
  }
}

5. One possible solution appears below.

public int countTwins() {
  return countTwins(this.overallRoot); 
}

private int countTwins(IntTreeNode root) {
  if (root == null) {
    return 0;
  } else {
    int twins = 0;
    if (root.left != null && root.right != null && root.left.data == root.right.data) 
      twins = 1;
    }
    return twins + countTwins(root.left) + countTwins(root.right);
  }
}

6. 
        Statement                       Output
        --------------------------------------------------
        var1.method1();                 Toast 1/Waffle 2
        var2.method1();                 Pancake 1/Poptart 1
        var3.method1();                 Toast 1/Waffle 2
        var4.method1();                 Pancake 1
        var5.method1();                 Pancake 1/Poptart 1
        var6.method1();                 compiler error
        var1.method2();                 Waffle 2
        var2.method2();                 Pancake 2/Pancake 1/Poptart 1
        var3.method2();                 Waffle 2
        var4.method2();                 Pancake 2/Pancake 1
        var5.method2();                 Pancake 2/Pancake 1/Poptart 1
        var6.method2();                 compiler error
        var3.method3();                 Waffle 3
        var5.method3();                 compiler error
        ((Waffle)var1).method3();       Waffle 3
        ((Poptart)var5).method3();      Poptart 3
        ((Toast)var3).method3();        compiler error
        ((Waffle)var2).method3();       runtime error
        ((Pancake)var2).method2();      Pancake 2/Pancake 1/Poptart 1
        ((Poptart)var6).method2();      runtime error

7. One possible solution appears 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. One possible solution appears below.
    public void switchPairsOfPairs() {
        if (front != null && front.next != null && 
            front.next.next != null && front.next.next.next != null) {
            ListNode current = front.next.next;
            front.next.next = current.next.next;
            current.next.next = front;
            front = current;
            current = current.next.next.next;
            while (current.next != null && current.next.next != null &&
                   current.next.next.next != null && 
                   current.next.next.next.next != null) {
                ListNode temp = current.next.next.next;
                current.next.next.next = temp.next.next;
                temp.next.next = current.next;
                current.next = temp;
                current = temp.next.next.next;
            }
        }
    }