June 4, 2003

Pages 228-236 (Section 6.1), pages 236-246 (Section 6.2)

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?