Mar 31, 2004

**Name:**________________________________________

- (1 pt)
*True or False:*A postorder traversal of a binary search tree visits the nodes of the tree in decreasing order of the keys.

- (1 pt)
What is the preorder traversal of this binary tree?

- (1 pt)
What is the asymptotic worst-case running time of the search
operation in a basic binary search tree with n keys?

- (2 pt) What is the asymptotic worst-case running time of the search operation in a balanced binary search tree with n keys?