""" QUESTION 1: General Knowledge

10 marks, ~15 minutes

(a) True or False. All binary search trees' branching factor must be 2.

TODO: write your answer below (True/False) [2 marks]

(b) Given that a binary tree's height is 9. What are the minimum and maximum numbers of nodes that this tree can have? Each answer must be a simple number (i.e., not a formula). Use your Python console as a calculator if needed.

Note: recall that the height of a tree is defined by counting _nodes_ instead of edges.

TODO: write your answer below. The minimum number of nodes possible: _____ [2 marks]

TODO: Write your answer below. The maximum number of nodes possible: _____ [2 marks]

(c) The following is the _preorder_ traversal of a Binary Search Tree:

18, 16, 13, 15, 19, 24, 22, 23

What is the size (number of nodes) of the subtree whose root is 16? You may answer "unknown" if the answer cannot be determined.

TODO: Write your answer below. The size of the subtree rooted at 16 is ______ [2 marks]

(d) A _reversely sorted_ linked list is a linked list where the nodes are sorted by their item values in a non-increasing order. For example, 148 -> 12 -> 8 -> 5 -> 3 is a reversely sorted linked list.

Which of the following operations for a reversely sorted linked list (of size n) has a worst-case time complexity that is _strictly_ lower than O(n)? (That is, it is either O(1) or O(log n)).

Note that the linked list must remain reversely sorted after each operation.

Choose all that apply.

A. Searching for a value B. Finding the maximum value C. Finding the minimum value D. Finding the second largest value E. Finding the second smallest value F. Inserting a new value G. Deleting a value if it exists H. Computing the average of all values

(Marking note: 1 mark will deducted for each missing choice or wrong choice, up to a maximum deduction of 2 marks).

TODO: write your choice(s) below (just the letters, A, B, etc.) [2 marks]

"""