EXERCISES ON BINARY SEARCH TREES

READING 
-------
Sedgewick, 217-223, 230-241, 477-508


EXERCISES
---------


 1. Sedgewick, Exercise 12.27

 2. Sedgewick, Exercise 12.33

 3. Sedgewick, Exercise 12.44

 4. Write a C function that prints all the keys less than a given value v 
    in a BST.

 5. Write a C function that returns the number of items in a BST with 
    key equal to a given key.  (Sedgewick, Exercise 12.49)



                 ------------------------------------
		 ANSWERS TO EXERCISES ON BINARY SEARCH TREES



 1. S E A Y Q U T I O N

 2.

 3.

 4.
        void smaller(link tree, int v) {
           if (tree == NULL)
              return;
           smaller(tree->l, v);
           if (tree->key >= v)
              return; 
           printf("%d ", v);
           smaller(tree->r, v);
        }



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

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

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