Reading material

Pages 246-257 (Section 6.3, excluding Section 6.3.5)

Additional material

Proof of Proposition 6.10 and 6.11 in PostScript and PDF.

InspectableBinaryTree
BinaryTree

Algorithm isBST(t):
   Input: binary tree whose nodes contains integers
   Output: Is t a binary search tree?
if t consists of a single node then
     result true
else
     result isBST(left subtree of t) isBST(right subtree of t) smallerOrEqual(left subtree of t, integer of root of t) greaterOrEqual(right subtree of t, integer of root of t)
return result

Algorithm smallerOrEqual(t, i):
   Input: binary tree whose nodes contains integers; an integer
   Output: (A n : n is a node of t : element of n <= i)
result element of root of t <= i
if t consists of more than one node then
     result result smallerOrEqual(left subtree of t, i) smallerOrEqual(right subtree of t, i)
return result

Algorithm greaterOrEqual(t, i):
   Input: binary tree whose nodes contains integers; an integer
   Output: (A n : n is a node of t : element of n >= i)
result element of root of t >= i
if t consists of more than one node then
     result result greaterOrEqual(left subtree of t, i) greaterOrEqual(right subtree of t, i)
return result

Question

What is the running time of smallerOrEqual, greaterOrEqual and isBST?