CSE143 Key to Final, Summer 2022

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

2.                                +------------+
                                  |   Monkey   |
                                  +------------+
                                 /              \
                                /                \
                               /                  \
                      +------------+         +------------+
                      |   Lizard   |         |   Rhino    |
                      +------------+         +------------+
                     /    
                    /     
                   /      
            +------------+  
            |   Fish     |
            +------------+
           /              \
          /                \
         /                  \
   +------------+      +------------+
   |   Cow      |      |   Husky    |
   +------------+      +------------+
                 \
                  \
                   \
             +------------+
             |   Eagle    |
             +------------+

3. One possible solution appears below.

    public Map<String, List<String>> commonHobbies(Map<String, 
                                                       List<String>> tas) {
        Map<String, List<String>> result = new TreeMap<>();
        for (String ta : tas.keySet()) {
            for (String hobby : tas.get(ta)) {
                if (!result.containsKey(hobby)) {
                    result.put(hobby, new ArrayList<>());
                }
                result.get(hobby).add(ta);
            }
        }
        return result;
    }

4. One possible solution appears below.

    public class TeamData implements Comparable<TeamData> {
        private String name;
        private int solved;
        private int totalTime;
        private int problems;
    
        public TeamData(String name, int problems) {
            this.name = name;
            this.problems = problems;
            this.totalTime = 0;
            this.solved = 0;
        }
    
        public void success(int time) {
            solved++;
            totalTime += time;
        }
    
        public String toString() {
            return name + " solved " + solved + " of " + problems + " in "
                + totalTime + " minutes";
        }
    
        public int solved() {
            return solved;
        }
    
        public int time() {
            return totalTime;
        }
    
        public int compareTo(TeamData other) {
            if (solved != other.solved) {
                return other.solved - solved;
            } else {
                return totalTime - other.totalTime;
            }
        }
    }

5. One possible solution appears below.

    public void printLevel(int target) {
        if (target < 1) {
            throw new IllegalArgumentException();
        }
        System.out.print("nodes at level " + target + " =");
        printLevel(overallRoot, target, 1);
        System.out.println();
    }

    private void printLevel(IntTreeNode root, int target, int level) {
        if (root != null) {
            if (level == target) {
                System.out.print(" " + root.data);
            } else {
                printLevel(root.left, target, level + 1);
                printLevel(root.right, target, level + 1);
            }
        }
    }

6.  Statement                    Output
    ------------------------------------------------------------
    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

7. One possible solution appears below.

    public void trimTo(int level) {
        if (level < 1) {
            throw new IllegalArgumentException();
        }
        overallRoot = trimTo(overallRoot, 1, level);
    }

    private IntTreeNode trimTo(IntTreeNode root, int curr, int level) {
        if (curr <= level && root != null) {
            if (root.left == null && root.right == null) {
                root = null;
            } else {
                root.left = trimTo(root.left, curr + 1, level);
                root.right = trimTo(root.right, curr + 1, level);
            }
        }
        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;
            }
        }
    }