ANSWERS TO EXERCISES ON BINARY SEARCH TREES




 1.  


     



 2.  




 3.     void smaller(link tree, int k) {
           if (tree == NULL)
              return;
           smaller(tree->left, k);
           if (tree->key < k) {
              printf("%d\n", k);
              smaller(tree->right, k);
           }
        }



 4. If the BST is built by Prog. 12.7 or 12.9, the equal keys are on the right.

        int searcheq(link x, Key k) {
           Key t = key(x->item);
           if (h == NULL)
              return 0;
           if less(k, t)
              return searcheq(x->left, k);
           else if eq(k, t)
              return searcheq(x->right, k) + 1;
           else 
              return searcheq(x->right, k);
        }

        int STsearcheq(Key k) {
           return searcheqR(tree, k);
        } 


 5. Be sure to handle case when left and/or right child is NULL.
           
        int isBST(link x) {
           if (x == NULL)
              return 1;
           else if (x->left == NULL && x->r == NULL)
              return 1;
           else if (x->left == NULL && x->key <= x->right->key)
              return isBST(x->right);
           else if (x->right == NULL && x->key >= x->left->key)
              return isBST(x->left);
           else if (x->key <= x->right->key  &&  x->key >= x->left->key)
              return isBST(x->left) && isBST(x->right);
           else
              return 0;
        }