Reading material

Pages 251-257 (Section 6.3.4)

Additional material

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

Question

Instead of returning just the answer to the question "Is t a binary search tree?", we now also compute the minimal integer stored in t and the maximal integer stored in t.

Algorithm isBST(t):
   Input: binary tree whose nodes contains integers
   Output: (Is t a binary search tree?, minimal integer stored in t, maximal integer stored in t)

Complete the recursive algorithm that computes all three at the same time. What is its worst-case running time?