Preview

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;
         }
			
         //not found
         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