Reading material
Pages 236-246 (Section 6.2)
Additional material
Proof of Proposition 6.10 and 6.11 in
PostScript and
PDF.
Question
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
-
all the integers stored in the left subtree of n
are smaller than or equal to the integer stored in n, and
-
all the integers stored in the right subtree of n
are greater than or equal to the integer stored in n.
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?