<![CDATA[
CSE143X Key to Final, Autumn 2023 handout #27
1. Preorder traversal 0, 3, 1, 2, 5, 8, 9, 4, 7, 6
Inorder traversal 1, 3, 5, 2, 8, 0, 9, 7, 4, 6
Postorder traversal 1, 5, 8, 2, 3, 7, 6, 4, 9, 0
2. +------------+
| Ephraim |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Ben | | Frank |
+------------+ +------------+
/ \ \
/ \ \
/ \ \
+------------+ +------------+ +------------+
| Adam | | Dan | | Gideon |
+------------+ +------------+ +------------+
/
/
/
+------------+
| Caleb |
+------------+
3. Method Call Value Returned
----------------------------------------
mystery(grid, 5) 5
mystery(grid, 3) 22
mystery(grid, 1) 24
4. One possible solution appears below.
public String acronymFor(List<String> words) {
String acronym = "";
for (String next : words) {
acronym += next.toUpperCase().charAt(0);
}
return acronym;
}
5. Binary Trees, 10 points. One possible solution appears below.
public int oddPathSum() {
return oddPathSum(overallRoot, 0);
}
public int oddPathSum(IntTreeNode root, int sum) {
if (root == null) {
return 0;
} else {
sum += root.data;
int result = oddPathSum(root.left, sum) +
oddPathSum(root.right, sum);
if (sum % 2 != 0) {
result++;
}
return result;
}
}
6. One possible solution appears below.
public Map<String, Set<List<String>>> acronyms(Set<List<String>> lists) {
Map<String, Set<List<String>>> result = new TreeMap<>();
for (List<String> words : lists) {
String acronym = acronymFor(words);
if (!result.containsKey(acronym)) {
result.put(acronym, new HashSet<>());
}
result.get(acronym).add(words);
}
return result;
}
7. One possible solution appears below.
public class ClockTime implements Comparable<ClockTime> {
private int hours;
private int minutes;
private String amPm;
public ClockTime(int hours, int minutes, String amPm) {
this.hours = hours;
this.minutes = minutes;
this.amPm = amPm;
}
public int compareTo(ClockTime other) {
if (!amPm.equals(other.amPm)) {
return amPm.compareTo(other.amPm);
} else if (hours != other.hours) {
return hours % 12 - other.hours % 12;
} else {
return minutes - other.minutes;
}
}
public int getHours() {
return hours;
}
public int getMinutes() {
return minutes;
}
public String getAmPm() {
return amPm;
}
public String toString() {
String result = hours + ":";
if (minutes < 10) {
result += "0" + minutes;
} else {
result += minutes;
}
result += " " + amPm;
return result;
}
}
8. 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;
}
9. One possible solution appears below.
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;
}
]]>