Reading material

Pages 236-246 (Section 6.2)

Additional material

Proof of Proposition 6.10 and 6.11 in PostScript and PDF.


Consider a binary trees whose nodes contain integers. We will call such a binary tree t a binary search tree if for each internal node n of t Write an algorithm that tests if a binary tree is a binary search tree.

Algorithm isBST(t):
   Input: binary tree whose nodes contains integers
   Output: Is t a binary search tree?