CS410, Summer 1998
Quiz #3
July 7

Consult no sources.  Put your answers below (obviously).

1. How long does it take to find the minimum element in a sorted array?
   How long does it take to find the minimum element in an unsorted array?

2. Draw three binary search trees using the numbers 1, 2, 3, 4, 5, 6.
   Make exactly one of the three as "tall" as possible.

3. How would you find the minimum element in a binary search tree?

ANSWERS
=======

1. sorted O(1)
   unsorted O(n)
(in your sleep)

One point each, no partial credit.

2. 1			3                      2
    \                 /   \                  /   \
     2               2     5                1     3
      \             /    /   \                     \
       3           1   4      6                     4
        \                                             \
         4                                             6
          \                                           /
           5                                         5
            \
             6
Many other answers possible, 2 points for each correct tree.  Exactly one
must have a height of 6.

3. x = root of tree
   while (x != null)
	x = x.left
   return x

   English description is equally acceptable.  Two points.