Problem 6

Problem Statement

Consider a rooted tree with nodes labeled $1, 2, 3, \ldots, n$. Devise a method for determining whether, given two arbitrary nodes in the tree, one node is an ancestor of the other. Your method should use time O(1) per input pair in the worst case.

Algorithm Idea

The algorithm consists of making a pre-order traversal on the tree, followed by a post-order traversal. An array of size n (one corresponding to each node) is created to store the results of the traversals. Values are assigned in the array in such a way that they receive a number which corresponds to the order in which each node is visited.

After the traversals have completed, the tree is never again used. Calculations are done using the pre-order and post-order values stored in the array(as indexed by node labels). These values are shown in Figure 1 near the node to which they correspond. If some node, x, is an ancestor of some node, y, then the pre-order value for x is less than the pre-order value of y and the post-order value for x is greater than the post-order value of y. If the above condition does not hold, then x is not an ancestor of y.

Pseudo Code

Let A := An array of size n
Let tree := An arbitrary rooted tree of size n
pre-order(tree, A)        {sets values in A[x].pre}
post-order(tree, A)        {sets values in A[X].post}

ancestor(x,y)
     if $(A[x].pre<A[y].pre & A[x].post>A[y].post)$
          return(true)
     else
          return(false)

 

Figure 1: (Pre-order,Post-order) values after both traversals.

Analysis

This algorithm is correct. To show this, the pre-order and post-order traversals must first be considered separately as follows:

pre-order :

A pre-order traversal will assign values into the array such that if we consider an arbitrary node, its ancestors and all sub-trees to the left of those ancestors will have a smaller value than the node in question. This follows directly from the definition of a pre-order numbering of nodes in a tree.

post-order :

A post-order traversal will assign values into the array such that if we consider an arbitrary node, its ancestors and all sub-trees to the right of those ancestors will have a larger value than the node in question. This follows directly from the definition of a post-order numbering of nodes in a tree.

These are the conditions which are tested in the ANCESTOR function. The ANCESTOR function takes the intersection of both conditions by requiring that they both hold. From this, the only nodes which validate this conjunction will be ancestors of the node in question.

The setup of this algorithm takes O(n) running time. This is because it consists of two tree traversals, one pre-order and one post-order. Each traversal requires O(n) running time. Therefore, the total time required is O(n).

The ANCESTOR function requires O(1) time. This is obvious, since it consists of 4 array lookups, and the conjunction of two tests of inequality -all of which require O(1).

Solution by William Totten