1) The add and remove methods of the AVL tree, as discussed in the lecture notes, are known as two-pass operations. What is meant by this?

A) Adding or removing an item requires two top-down traversals of the tree. The first pass adds or removes an item, while the second pass fixes any imbalances that may occur as a result of adding or removing an item.

B) Adding or removing an item requires a top-down traversal of the tree to add or remove an item, followed by a bottom-up traversal to fix any imbalances that may occur as a result of adding or removing an item.

C) Adding or removing an item requires two bottom-up traversals of the tree. The first pass adds or removes an item, while the second pass fixes any imbalances that may occur as a result of adding or removing an item.

D) Adding or removing an item requires a bottom-up traversal of the tree to add or remove an item, followed by a top-down traversal to fix any imbalances that may occur as a result of adding or removing an item.

2) In the algorithm for removing a node from a binary search tree, if the node being removed has two children, the algorithm:

A) sets the corresponding child reference of the parent of the node being removed to null.

B) sets the corresponding child reference of the parent of the node being removed to the child of the node being removed.

C) sets the item being referenced by the node being removed to that of the least node in the left subtree of the node being removed, then sets the corresponding reference of that node's parent to null.

D) sets the item being referenced by the node being removed to that of the least node in the right subtree of the node being removed, then sets the corresponding reference of that node's parent to null.

3) In the context of binary search trees, what is the average case running time for the remove operation?

A) O(1)

B) O(log N)

C) O(N)

D) O(N log N)

4) In the context of binary search trees, what is the worst case running time for the add operation?

A) O(1)

B) O(log N)

C) O(N)

D) O(N log N)