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