Autocomplete
4a. The local variable pq maintains a priority queue such that the code on lines 59-61 removes the elements in order from least-weight to highest-weight. Using the values from the previous questions:
Explain why the values removed in that example will be in the order: 40, 50, 55, 60.
We remove the lightest weight first.
What should the method do in the base case? That is, suppose there is only 1 value in the list or the list is null, what should the method return?
If there is only 1 value, return that node. If the list is null, return null
Draw or describe a binary search tree with height 4 that has exactly 5 nodes
Example: (1)-(2)-(3)-(4)-(5). All nodes are right children of the previous
4. Which words can be added in the left subtree of Salmon?
none
What is the post-order traversal of the tree diagrammed above (and reproduced here)
Crow, bobcat, dingo, octopus, narwhal, salmon, penguin, moose
3. If Term weight values of 20, 30, 40, 50, 60, 55, 32 are added to pq when k is 4, so that only four values are stored in the priority queue, what four values will be in the priority queue after all seven Term weights are added? Note that after 20,30,40,50 are added there are only four values in the priority queue.
40,50,60,55
2. What should the recursive call be? This should be a single line of code.
allSums(list.next)
2. Draw or describe a binary search tree with height 3 that has exactly 15 nodes
Completely full binary search tree, so each node has two children on either side up to level 3
2. Which words can be added in the left subtree of Crow?
cougar
2. What is the pre-order traversal of the tree?
Moose, dingo, bobcat, crow, penguin, narwhal, octopus, salmon
1. The for-loop shown on lines 42-52 loops over an instance variable array myTerms as shown to the right. Explain the purpose of lines 43-44 in this loop.
It makes sure we only consider terms that start with the given prefix.
3. After the recursive call, what do you need to update before returning?
Update the value of the current ListNode to be the value of the original list node + the value of all of the following ListNodes that you get by returning the cumulative sum through recursive calls.
3. How many distinct binary search trees are there with nodes with the values [1,2,3]?
5
If 2 is the root, there is only one possible tree (1 on the left, 3 on the right). If 1 or 3 is the root, then they each have 2 possible trees depending on if 2 is inserted first.
1. Which words can be added to be in the right subtree of Dingo? You can list them as something like mule..otter, e.g., provide the first and last words.
dog...mole
2. The code in lines 46-51 removes the smallest element from PriorityQueue pq if that element's weight is less than the weight of the Term t; then Term t is added to the priority queue. What part of the definition of variable pq on lines 40-41 ensures that the smallest value is removed by the call pq.remove()?
Comparator.comparing(Term::getWeight) ensures that the pq uses the weight of the terms, and it ensures that the smallest weight element is removed first.
4. What is the maximum height of a search tree with N nodes? Use big-Oh
O(N)- completely unbalanced tree
5. Which words can be added in the right subtree of Salmon?
tiger..zebra
3. If the recursive calls in the code for inOrder are swapped, so that the call inOrder(t.right) occurs first, then the print statement, then the call to inOrder(t.left), what is the traversal?
Salmon, penguin, octopus, narwhal, moose, dingo, crow, bobcat
4b. The local variable pq maintains a priority queue such that the code on lines 59-61 removes the elements in order from least-weight to highest-weight. Using the values from the previous questions:
Explain why the values are added to the front of the linked list on line 60.
We want the final list to be in descending order by weight. Adding to the front of the linked list ensures that we add the last element to the front.
5. What is the minimum height of a search tree with N nodes? Use big-Oh
O(log n)- perfectly balanced tree
3. Which words can be added in the right subtree of Octopus?
orangutan..pelican