CS 61B Spring 2021
1 Tree-versals
Traversals, Tries, Heaps Discussion 9: March 15, 2020
10
3 12
1 7 11 14
13 15
Write the pre-order, in-order, post-order, and level-order traversals of the above binary search tree.
Pre-order: 103171211141315 In-order: 137101112131415 Post-order: 173111315141210 Level-order (BFS): 10 3 12 1 7 11 14 13 15
2 Graphs
C BFG
D AE
(a) Write the graph above as an adjacency matrix, then as an adjacency list. What would be different if the graph were undirected instead?
2
Traversals, Tries, Heaps
(b)
Write the order in which DFS pre-order graph traversal would visit nodes in the undirected graph above, starting from vertex A. Break ties alphabetically. Extra: Do the same for DFS post-order and BFS
DFS preorder: ABCFDE (G)
DFS postorder: FCBEDA (G)
BFS: ABDCEF (G)
Explanations
DFS preorder and postorder: To compute this, we maintain a stack of nodes, and a marked set. As soon as we add something to our stack, we note the down for preorder. The top node in our stack represents the node we are currently on, and the marked set represents nodes that have been visited. After we add a node to the stack, we visit its lexicographically next unmarked child. If there is none, we pop the topmost node from the stack and note it down for postorder. Note that there are two ways DFS could run: with restart or without; DFS with restart is the version where if we have exhausted our stack, and still have unmarked nodes left, we restart on the next unmarked node.
Stack (bottom-top), MarkedSet, Preorder, Postorder.
A. {A}. A. –
AB. {AB}. AB. –
ABC. {ABC}. ABC. –
ABCF. {ABCF}. ABCF. –
ABC. {ABCF}. ABCF. F
Matrix:
ABCDEFG <- end node
A 0101000
B 0010000
C 0000010
D 0100110
E 0000010
F 0000000
G 0000010
ˆ start node
For the undirected version of the graph, the representations look a bit more symmetric. For your reference, the representations are included below: Matrix:
ABCDEFG <- end node
A 0101000
B 1011000
C 0100010
D 1100110
E 0001010
F 0011101
G 0000010
ˆ start node
List:
A: {B, D}
B: {A, C, D}
C: {B, F}
D: {A, B, E, F}
E: {D, F}
F: {C, D, E, G}
G: {F}
List:
A: {B,
B: {C}
C: {F}
D: {B,
E: {F}
F: {}
G: {F}
D}
E, F}
AB. {ABCF}. ABCF. FC.
A. {ABCF}. ABCF. FCB.
AD. {ABCFD}. ABCFD. FCB.
ADE. {ABCFDE}. ABCFDE. FCB.
AD. {ABCFDE}. ABCFDE. FCBE.
A. {ABCFDE}. ABCFDE. FCBED.
\-. {ABCFDE}. ABCFDE. FCBEDA.
If DFS restarts on unmarked nodes, the following happens in the last line. Otherwise, we do not proceed further.
G. {ABCFDEG}. ABCFDEG. FCBEDAG.
BFS: Start at the provided start node. Note it down, and mark it. Now, consider all nodes that are 1-hop (i.e. one edge) away from the start node. Write all of them down, and mark all of them. Next, consider all unmrked nodes that are 1-hop away from the nodes that were 1-hop away from the start (i.e., 2 hops away from the start). And so on. Note that unlike DFS, BFS uses a queue.
BFS, MarkedSet.
A. {A}.
A BD. {ABD}.
A BD CEF. {ABDCEF}.
If BFS restarts, the following happens at the end. Otherwise, we do not proceed further..
A BD CEF (G). {ABDCEFG}.
Traversals, Tries, Heaps 3
4
Traversals, Tries, Heaps
3
(a)
1 2 3 4 5 6 7 8
Heaps of Fun
Assume that we have a binary min-heap (smallest value on top) data struc- ture called MinHeap that has properly implemented the insert and removeMin methods. Draw the heap and its corresponding array representation after each of the operations below:
MinHeap
h.insert(‘h’);
h.insert(‘d’);
h.insert(‘b’);
h.insert(‘c’);
h.removeMin();
h.removeMin();
f f
h
d
hf b
df
h
b
c
f
df h
hd
c
d hf
(b) Your friendly TA Tony challenges you to quickly implement an integer max- heap data structure. However, you already have your MinHeap and you don’t feel like writing a whole second data structure. Can you use your min-heap to mimic the behavior of a max-heap? Specifically, we want to be able to get the largest item in the heap in constant time, and add things to the heap in Θ(log n) time, as a normal max heap should.
Hint: Although you cannot alter them, you can still use methods from MinHeap. Yes. For every insert operation, negate the number and add it to the min-heap.
For a removeMax operation call removeMin on the min-heap and negate the number returned. Any number negated twice is itself (with one exception in Java, −2−31), and since we store the negation of numbers, the order is now reversed (what used to be the max is now the min).
Traversals, Tries, Heaps 5