Reading material

Additional material

"More output"

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)
else
     (isBST_left, min_left, max_left) isBST(left subtree of tree)
     (isBST_right, min_right, max_right) isBST(right subtree of tree)
     isBST isBST_left isBST_right max_left <= key of root of tree <= min_right
     min min(key of root of tree, min_left, min_right)
     max min(key of root of tree, max_left, max_right)
     result (isBST, min, max)
return result

"More input"

Algorithm isBST(tree, min, max):
   Input: a binary tree whose nodes contains keys; key; key
   Output: Is tree a binary search tree? (A node : node is a node of tree : min <= key of node <= max)
if tree has one node then
     result min <= key of root of tree <= max
else
     result min <= key of root of tree <= max isBST(left subtree of tree, min, min(key of root of tree, max)) isBST(right subtree of tree, max(min, key of root of tree), max)
return result

Implementation of a binary tree by means of an array

Algorithm removeAboveExternal(node):
   Precondition: node is external and different from the root
   Input: a node of the binary tree
   Postcondition: node and its parent have been removed from the tree and the sibling of node takes the place of its parent
   Output: the element of the parent of node
index index of node
parent index div 2
element element of tree[parent]
sibling index + 1 - 2 * (index mod 2)
move(sibling, parent)
size size - 2
return element

Algorithm move(old, new):
   Precondition: old is the index of a child of the node with index new
   Input: two indices of nodes
   Postcondition: the subtree rooted at node with index old replaces the subtree rooted at node with index new
tree[new] tree[old]
if tree[old] is an internal node then
     move(2 * old, 2 * new)
     move(2 * old + 1, 2 * new + 1)
else
     tree[2 * new] empty
     tree[2 * new + 1] empty

Question