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.