Reading material

Pages 263-265 (Section 6.4.1)

Additional material

Implementation of a binary tree by means of an array in PostScript and PDF

Algorithm isBST(tree):
   Input: a binary tree whose nodes contains keys
   Output: (Is tree a binary search tree?, minimal key stored in tree, maximal key stored in tree)
if tree has one node then
     result (true, key of root of tree, key of root of tree)
     (isBSTleft, minleft, maxleft) isBST(left subtree of tree)
     (isBSTright, minright, maxright) isBST(right subtree of tree)
     isBST isBSTleft isBSTright maxleft <= key of root of tree <= minright
     min min(key of root of tree, minleft, minright)
     max min(key of root of tree, maxleft, maxright)
     result (isBST, min, max)
return result


Give the pseudocode for removeAboveExternal in the implementation of a binary tree with an array.