This section presents a generalization of the parallel prefix
computation to binary trees. We present two kinds of *treefix*
computations--*rootfix* and *leaffix*--and show how they can
be implemented by an -step conservative algorithm that uses
space, where *n* is the number of nodes in the input tree. As
we shall see in Section 7, treefix computations can greatly
simplify the description of many parallel graph algorithms in the
literature, and moreover, treefix computations can be performed by
conservative algorithms.

We begin with a definition of treefix computation.
**Definition.** Let be a domain with a
binary associative operation and an identity
. Let *T* be a rooted, binary tree in which each vertex
has an assigned input value . The *rootfix*
problem is to compute for each vertex with parent *j*, the
output value , where if *i* is the root.
The *leaffix* problem is to compute for each vertex with
left child *j* and right child *k*, the output value , where if *i* has no left child and
if *i* has no right child.
Simple examples of treefix problems are computing the depth of each
vertex in a rooted binary tree and computing the size of each subtree.
These and other examples appear in the next section.

Like the prefix computation on lists, treefix computations can be performed directly on the contraction tree. For simplicity, however, we describe a recursive version.

**Proof:**
Both treefix computations are performed by executing a single
contraction step on the input tree *T* to produce a contracted tree .
Each node in is assigned an input value, and the treefix computation is
executed recursively on . The contracted tree is then expanded
to yield *T* once again, and the output value of each node in *T* is
computed from the input values of *T* and the output values of .

The algorithm for leaffix is based on each node *i* maintaining a
value which has the form , where
are elements of the domain, and the character
`` '' represents symbolically a slot to be filled in with a
value. The number of slots is equal to the number of children of the
node, and each slot corresponds to a specific child. When a parent
and child pair during the course of the leaffix algorithm, the value
of the child is substituted into the corresponding slot in the value
of its parent. For example, suppose node *i* pairs with its right
child *j*, where the value of *i* is and the
value of *j* is . The value of the merged
node *k* is computed from and by substituting into
the second slot in , yielding the value . The operations are carried out
immediately so that has the proper form.

The leaffix algorithm initializes each node *i* by ,
, or depending on the
number of children of node *i*. The algorithm then proceeds as
follows. At the end of a contraction step, each node *k* in that
results from the merging of parent *i* and child *j* computes its
value by substituting into the appropriate slot of .
The leaffix algorithm is then performed recursively on using the
*s* values as inputs and yielding *y* values as output. (The *y*
values contain no slots and are simply elements of the domain
.) During the expansion step, the parent node *i* sets
. Each child node *j* gets its output value by
substituting the *y* values of its children into the slots of .

In the rootfix algorithm, each node *i* maintains a value , as in
the leaffix algorithm, but each now has the general form
, and the slot of a node corresponds to the node's
parent. The rootfix algorithm initializes each node *i* by
, except for the root *r* which performs . After the pairs have been determined for the contraction step,
each node *j* that is the child in a pair, and which itself has a
child, substitutes in the appropriate slot of its child's value.
At the end of a contraction step, each node *k* in that resulted
from the merging of parent *i* and child *j* computes its value by
. The rootfix algorithm is then performed recursively
on , yielding *y* values as output. During the expansion step,
the parent node *i* sets . Each child node *j* gets its
output value by substituting into the slot of .

The time and space bounds claimed in the theorem are apparent by
inspection. Each step of a treefix algorithm adds only a constant
amount of work to a corresponding step in the tree contraction and
expansion algorithms. The additional space required by the treefix
algorithms is the space per node for the *x*, *y*, and *s*
values.

to .667emto .667em

Thu Jul 25 19:12:36 EDT 1996