Reading material

Pages 249-250 (Section 6.3.3), pages 236-246 (Section 6.2.1-6.2.4), pages 251-257 (Section 6.3.4)

Additional material

Proof of Proposition 6.10 and 6.11 in PostScript and PDF.

Variant function

Before we can reason inductively about recursive algorithms, we need to prove that the algorithm terminates. To show that there is no infinite recursion without tracing through the actual computation, we introduce a variant function. This function maps each instance of the parameters satisfying the precondition to a natural number. That is, it is a function from instances to natural numbers. Consider for example

Algorithm factorial(n):
   Input: integer
   Output: n!
   Precondition: n > 0
if n = 1 then
     result 1
else
     result n * factorial(n - 1)
return result

The variant function variant has to map each instance of the parameters satisfying the precondition, in this example a positive integer, to a natural number. This natural number can be thought of as an upperbound of the number of recursive calls this instance gives rise to. For example, factorial(n) gives rise to n - 1 recursive calls.

To prove that a recursive algorithm does not lead to infinite recursion, it is enough to find a variant function variant with the following two properties:

For example, for factorial the above properties amount to: The function variant(n) = n - 1 satisfies the above two properties. Note that the variant function is not unique. For example, the variant function defined by variant(n) = 2n - 2 also satisfies the above properties.

Let us have a look at another example. Consider the following algorithm.

Algorithm numberOfNodes(node):
   Input: node of a binary tree
   Output: number of nodes of the subtree rooted at node
if node is a leaf then
     result 1
else
     result 1+ numberOfNodes(left child of node) + numberOfNodes(right child of node)
return result

In this example, the instances of the parameters are nodes of a binary tree. The variant function variant has to satisfy

Consider the function variant(node) = number of internal nodes of the subtree rooted at node. One can easily check that it satisfies the above properties, and hence prove that the recursive algorithm eventually terminates.

Now consider the following algorithm.

Algorithm f(n):
   Input: integer
   Output: 1
   Precondition: n > 0
if n = 1 then
     result 1
else
     result f(n + 1)
return result

Again the instances are positive integers. In this case, the variant function variant should satisfy

We cannot find such a function. This is not surprising. The algorithm does not terminate for any integer greater than 1.

Binary search trees

The definition of a binary search tree can be found on page 382 of the textbook (this definition may be different from one used in 1030). Next, we discuss three recursive algorithms that test if a given binary tree whose nodes contains keys is a binary search tree.

Algorithm isBST(tree):
   Input: a binary tree whose nodes contains keys
   Output: tree is a binary search tree?
if tree has one node then
     result true
else
     result isBST(left subtree of tree) isBST(right subtree of tree) areLessThanOrEqual(key, left subtree of tree) areGreaterThanOrEqual(key, right subtree of tree)
return result

Algorithm areLessThanOrEqual(key, tree):
   Input: key and a binary tree whose nodes contains keys
   Output: for all nodes node : node is node of tree : key of node <= key?
if tree has one node then
     result key of root of tree <= key
else
     result key of root of tree <= key areLessThanOrEqual(key, left subtree of tree) areLessThanOrEqual(key, right subtree of tree)
return result

The recursive algorithm areGreaterThanOrEqual can be defined similarly (left as an easy exercise). The worst-case running time of isBST(tree) is O(n2), where n is the number of nodes of tree. The worst-case running time of the next algorithm is O(n).

Algorithm isBST(tree):
   Input: a binary tree whose nodes contains keys
   Output: (tree is 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
     (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

Questions

Give a variant function for
Algorithm height(node):
   Input: node of a binary tree
   Output: height of node (length of the longest path from node to an external node)
if node is a leaf then
     result 0
else
     result 1 + max { height(left child of node), height(right child of node) }
return result

Complete the following algorithm.
Algorithm isBST(tree, min, max):
   Input: a binary tree whose nodes contains keys and a minimal and maximal key
   Output: tree is a binary search tree? for all node : node is a node of tree : min <= key of node <= max?
Which values should one take for min and max to check if tree is a binary search tree?