May 22, 2001

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:

variant maps instances of the base case(s) to 0.
variant maps (the instances of) recursive calls to a smaller number than (the instance of) original call.

For example, for factorial the above properties amount to:

variant(1) = 0.
variant(n - 1) < variant(n).

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

variant(node) = 0 if node is a leaf and
variant(left child of node) < variant(node) and variant(right child of node) < variant(node) if node is not a leaf.

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

variant(1) = 0.
variant(n + 1) < variant(n).

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(n²), 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
     (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

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?