# 03 - Binary Tree Search

1. Fill in the blanks for the following overview of the Binary Search Tree
```A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties ?

The left sub-tree of a node has a key ______ than or equal to its parent node's key.

The right sub-tree of a node has a key _______ than to its parent node's key```

greater / less

greater / greater

less / greater

less / less

2. Which statement is true of the following search algorithm?
```struct node* search(int data){
struct node *current = root;
printf("Visiting elements: ");

while(current->data != data){

if(current != NULL) {
printf("%d ",current->data);

//go to left tree
if(current->data > data){
current = current->leftChild;
}  //else go to right tree
else {
current = current->rightChild;
}

if(current == NULL){
return NULL;
}
}
}

return current;
}```

Start searching at the left most node of the left sub tree, then work your way to the right

Start searching from the right-most node (right sub tree), then work your way to the root

Start searching from the root node. If the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree.

Start searching at the last index (e.g. leaf node) and work backwards in a tree search

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

exclusively recursively programmed

node-based

static

iterative

4. The following is a utility function to search a given key in BST. What should go where the ??????'s are?
```def search(root,key):

# Base Cases: root is null or key is present at root
if root is None or root.val == key:
????????

# Key is greater than root's key
if root.val < key:
return search(root.right,key)

# Key is smaller than root's key
return search(root.left,key) ```

search(root)

key()

return root

root.val()

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

no

minimal

only descending (greatest to smallest)

sorted

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

only recursively

only using for loops, due to the nature of the root node and required iterations

recursively or iteratively

in only one way

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

> root

1

NULL

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

the root

the leaf nodes

the left subtree

the right subtree

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

the root

the leaf nodes

the left subtree

the right subtree

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 ____________________________________

then the key is not present in the tree

then it returns to the root to start searching again

then it starts at the left most node again to repeat the search

the it starts at the beginning again

11. The following is an example (Python) of a _____________ binary search tree algorithm
```def search_1(key, node):
if node is None or node.key == key:
return node
if key < node.key:
return search_1(key, node.left)
# key > node.key
return search_1(key, node.right)```

iterative

recursive

root first

left leaf node first

12. In the following iterative example, what should replace the ???????'s
```def search_iteratively(key, node):
current_node = node
while current_node is not None:
??????????????????
return current_node
if key < current_node.key:
current_node = current_node.left
else: # key > current_node.key:
current_node = current_node.right
return current_node```

if key < current_node.key

if key == current_node.key:

if key > current_node.key:

if key ==NULL:

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

O(1)

O(n)

O(log n)

O(n x 2)

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

FALSE

TRUE

15. In a ______ tree, the minimum is located at the node farthest left, while the maximum is located at the node farthest right
```findMinimum(node)
if node is NULL
return EMPTY_TREE
min := node
while min.left is not NULL
min := min.left
return min.key```

sorted

iteratively programmed

unsorted

recursively programmed