1. Fill in the blanks for the following overview of the Binary Search Tree

2. Which statement is true of the following search algorithm?

3. A Binary Search Tree is a_________ data structure where each node contains a key and two subtrees, the left and right

4. The following is a utility function to search a given key in BST. What should go where the ??????'s are?

5. Binary search trees keep their keys in _______ order, so that lookup and other operations can use the principle of binary search

6. Searching a binary search tree for a specific key can be programmed _______________________-

7. In a binary search, we begin by examining the root node. If the tree is ______, the key we are searching for does not exist in the tree

8. In a binary search, if the key is less than that of the root, we search _________________

9. In a binary search, if the key is greater than that of the root, we search

10. In a binary search the process of searching is repeated until the key is found or the remaining subtree is null. If the searched key is not found after a null subtree is reached ____________________________________

11. The following is an example (Python) of a _____________ binary search tree algorithm

12. In the following iterative example, what should replace the ???????'s

13. In the worst case, binary search trees can have _____ height, when the unbalanced tree resembles a linked list (degenerate tree)

14. The worst-case time complexity for searching a binary search tree is the height of the tree, which can be as small as O(log n) for a tree with n elements

15. In a ______ tree, the minimum is located at the node farthest left, while the maximum is located at the node farthest right