CS 61B Midterm 2
Fall 2025 Thursday, November 6, 2025
Solutions last updated: 11/10/25
Print Your Name:
Print Your Student ID:
Print Student name to your left:
Print Student name to your right:
You have 110 minutes. There are 7 questions of varying credit. (100 points total)
Question: 1 2 3 4 5 6 7 Total
Points: 15 16 15 15 9 16 14 100
For questions with circular bubbles, select only For questions with square boxes, you may select
one choice (there is only one correct answer). one or more choices (select all that apply).
Unselected option (completely unfilled) You can select
Don’t do this (it will be graded as incorrect) multiple squares
Only one selected option (completely filled) Don’t do this (it will be graded as incorrect)
• Anything you write outside the answer boxes or you cross out will not be graded. If you write multiple
answers or your answer is ambiguous, we will grade the worst interpretation.
• Unless otherwise specified, all data structures and algorithms behave according to their implementation
in lecture, with no additional optimizations.
• If an implementation detail (e.g. tiebreaking scheme, linked list topology) or a Java library not on the
reference card (e.g. Google Truth) is relevant, it will be explicitly noted in the question.
• You may write at most one statement per blank and you may not use more blanks than provided.
• Your answer will be reformatted according to the 61B/61BL style guidelines. For example, any method,
constructor, or if-statement requires at least three lines for the purposes of determining line count.
• You may not use ternary operators, lambdas, streams, or multiple assignment.
• Unless otherwise specified, you may assume that everything on the reference card has been imported.
Read the honor code below and sign your name.
By signing below, I affirm that all work on this exam is my own work. I have not referenced any
disallowed materials, nor collaborated with anyone else on this exam. I understand that if I cheat on
the exam, I may face the penalty of an “F” grade and a referral to the Center for Student Conduct.
Page 1 of 30
,Sign your name:
Q1 Treevia (15 points)
Consider the tree below. The letters represent unknown integer values, and all 10 values are unique.
A
B C
D E F G
H I J
Q1.1 (3 points) Suppose the tree represents a max heap. Which could be the third-largest value?
A B C D E F G H I J
Solution:
First, note that all 10 values are unique (no duplicates). For simplicity, we’ll assume the values
are 1 through 10, inclusive.
A: False. A is the largest value, so it cannot be the third-largest value.
B: True. For example, you could assign A=10, B=8, C=9.
C: True. For example, you could assign A=10, B=9, C=8.
D, E, F, G: True. You can assign the node (D, E, F, G) as 8, then its parent as 9, then its grandparent
(A) as 10.
H, I, J: False. H has 3 ancestors (D, B, A), which means that there are at least 3 values greater than
H. Therefore, H cannot be the third-largest value. The same argument applies for I and J.
Q1.2 (2 points) Suppose the tree represents a binary search tree. Which could be the third-largest value?
A B C D E F G H I J
Solution:
The three largest items are C, F, G, since they are the items greater than A.
Out of these three items, F is smaller than C and G. Therefore, F is the third-largest item.
Page 2 of 30
, (Question 1 continued…)
Q1.3 (2 points) Suppose the tree represents a binary search tree. We delete A using Hibbard deletion.
Which nodes could become the new root?
B C D E F G H I J
Solution:
In Hibbard deletion, the new root could be the predecessor or successor of A.
The predecessor (largest item out of everything smaller than A) is E.
The successor (smallest item out of everything greater than A) is F.
Q1.4 (2 points) Suppose we perform an in-order tree traversal of the subtree rooted in B. Which will be
the last node visited?
B D E H I J
Solution:
The in-order traversal order is H, D, I, B, J, E.
Q1.5 (2 points) The statement “F is strictly greater than J” is always true if the tree represents a ________.
Select all options that could go in the blank.
Min heap Max heap BST None
Solution:
A min-heap where F is not greater than J: A max-heap where F is not greater than J:
1 10
2 3 9 8
4 5 6 7 7 6 1 4
8 9 10 3 2 5
In the BST, F > A, and A > J, so we have F > J.
Page 3 of 30
Fall 2025 Thursday, November 6, 2025
Solutions last updated: 11/10/25
Print Your Name:
Print Your Student ID:
Print Student name to your left:
Print Student name to your right:
You have 110 minutes. There are 7 questions of varying credit. (100 points total)
Question: 1 2 3 4 5 6 7 Total
Points: 15 16 15 15 9 16 14 100
For questions with circular bubbles, select only For questions with square boxes, you may select
one choice (there is only one correct answer). one or more choices (select all that apply).
Unselected option (completely unfilled) You can select
Don’t do this (it will be graded as incorrect) multiple squares
Only one selected option (completely filled) Don’t do this (it will be graded as incorrect)
• Anything you write outside the answer boxes or you cross out will not be graded. If you write multiple
answers or your answer is ambiguous, we will grade the worst interpretation.
• Unless otherwise specified, all data structures and algorithms behave according to their implementation
in lecture, with no additional optimizations.
• If an implementation detail (e.g. tiebreaking scheme, linked list topology) or a Java library not on the
reference card (e.g. Google Truth) is relevant, it will be explicitly noted in the question.
• You may write at most one statement per blank and you may not use more blanks than provided.
• Your answer will be reformatted according to the 61B/61BL style guidelines. For example, any method,
constructor, or if-statement requires at least three lines for the purposes of determining line count.
• You may not use ternary operators, lambdas, streams, or multiple assignment.
• Unless otherwise specified, you may assume that everything on the reference card has been imported.
Read the honor code below and sign your name.
By signing below, I affirm that all work on this exam is my own work. I have not referenced any
disallowed materials, nor collaborated with anyone else on this exam. I understand that if I cheat on
the exam, I may face the penalty of an “F” grade and a referral to the Center for Student Conduct.
Page 1 of 30
,Sign your name:
Q1 Treevia (15 points)
Consider the tree below. The letters represent unknown integer values, and all 10 values are unique.
A
B C
D E F G
H I J
Q1.1 (3 points) Suppose the tree represents a max heap. Which could be the third-largest value?
A B C D E F G H I J
Solution:
First, note that all 10 values are unique (no duplicates). For simplicity, we’ll assume the values
are 1 through 10, inclusive.
A: False. A is the largest value, so it cannot be the third-largest value.
B: True. For example, you could assign A=10, B=8, C=9.
C: True. For example, you could assign A=10, B=9, C=8.
D, E, F, G: True. You can assign the node (D, E, F, G) as 8, then its parent as 9, then its grandparent
(A) as 10.
H, I, J: False. H has 3 ancestors (D, B, A), which means that there are at least 3 values greater than
H. Therefore, H cannot be the third-largest value. The same argument applies for I and J.
Q1.2 (2 points) Suppose the tree represents a binary search tree. Which could be the third-largest value?
A B C D E F G H I J
Solution:
The three largest items are C, F, G, since they are the items greater than A.
Out of these three items, F is smaller than C and G. Therefore, F is the third-largest item.
Page 2 of 30
, (Question 1 continued…)
Q1.3 (2 points) Suppose the tree represents a binary search tree. We delete A using Hibbard deletion.
Which nodes could become the new root?
B C D E F G H I J
Solution:
In Hibbard deletion, the new root could be the predecessor or successor of A.
The predecessor (largest item out of everything smaller than A) is E.
The successor (smallest item out of everything greater than A) is F.
Q1.4 (2 points) Suppose we perform an in-order tree traversal of the subtree rooted in B. Which will be
the last node visited?
B D E H I J
Solution:
The in-order traversal order is H, D, I, B, J, E.
Q1.5 (2 points) The statement “F is strictly greater than J” is always true if the tree represents a ________.
Select all options that could go in the blank.
Min heap Max heap BST None
Solution:
A min-heap where F is not greater than J: A max-heap where F is not greater than J:
1 10
2 3 9 8
4 5 6 7 7 6 1 4
8 9 10 3 2 5
In the BST, F > A, and A > J, so we have F > J.
Page 3 of 30
