Reading material

If you use the first edition of the textbook, follow the reading material in orange. If you use the second edition, follow the reading material in brown.

(1st) pages 250-256 (Section 7.1.2-7.2.2)

(2nd) pages 340-341 (Section 8.2), pages 357-361 (Section 8.4, 8.5)

Additional material

Implementation of a dictionary by means of an array in pseudocode: PostScript and PDF

EqualityTester
IntegerEqualityTester
ArrayDictionary
DictionaryFullException

Question

Give a recursive algorithm to test if a binary tree is a binary search tree. What is the running time of the algorithm?