Question 9. Binary search trees [9]

Suppose we have a binary search tree which uses integer keys, duplicates are not permitted, and empty (NULL) trees are considered valid.

The tree nodes are defined using the node struct below, with our usual assumption that for a valid binary search tree smaller keys must go into left subtrees, while larger keys must go into right subtrees.

struct node {
   int key;
   node *left, *right;
};

Study the checkTree function defined below. It is meant to return true if a subtree has a valid binary search tree structure, and return false otherwise. The function implementation is not entirely correct.

bool checkTree(node *t, int minVal, int maxVal) {
   // an empty tree is valid
   if (t == NULL) return true;
   // make sure this key is valid 
   else if ((t->key < minVal) || (t->key > maxVal)) {
      cout << "Error detected at node " << t->key << endl;
      return false;
   }
   // make sure the values in the left subtree are ok
   else if (!checkTree(t->left, minVal, t->key)) {
      cout << "Which was the left child of " << t->key << endl;
      return false;
   }
   // make sure the values in the right subtree are ok
   else if (!checkTree(t->right, t->key, maxVal)) {
      cout << "Which was the right child of " << t->key << endl;
      return false;
   }
   // this entire subtree is ok
   else return true;
}

For each of the two trees depicted below, show any the output the call checkTree(root, 0, 10) would produce (assuming root was the pointer to the root of the relevant tree). If the call would produce no output then explain why it would fail to detect the error(s) in the tree.

Tree 1: 5 / \ 3 4 / \ 2 6

Tree 2: 3 / \ 1 4 \ / \ 3 5 (node 3 is both the right child of node 1 and the left child of node 4)