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

  less / greater

  greater / greater

  greater / less

  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 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

  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

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

  node-based

  exclusively recursively programmed

  iterative

  static

 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)

  root.val()

  search(root)

  key()

  return root

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

  minimal

  sorted

  no

  only descending (greatest to smallest)

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

  only recursively

  recursively or iteratively

  in only one way

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

 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

  1

  NULL

  

  > root

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

  the left subtree

  the leaf nodes

  the right subtree

  the root

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

  the right subtree

  the leaf nodes

  the left subtree

  the root

 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 it returns to the root to start searching again

  then the key is not present in the tree

  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)

  left leaf node first

  iterative

  recursive

  root 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 ==NULL:

  if key > current_node.key:

  if key < current_node.key

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

  O(log n)

  O(n x 2)

  O(1)

  O(n)

 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

  TRUE

  FALSE

 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

  unsorted

  recursively programmed

  iteratively programmed

  sorted


Report an error