一个图的欧拉回路是通过图的每条边一次一个回路，当然，在此过程中它可以多次访问一个结点。根据图论算法可知，一个有向连通图具有欧拉回路当且仅当对所有结点v，v的出度等于v的入度。因为无向图每条无向边(u，v)对应于相应的有向图中的两条边(u，v)和(v，u)，因此任何无向连通图改成的有向图均包含欧拉回路，这对无向树也自然成立。
(a)
(b)
图4 运用欧拉回路技术来计算每个结点在二叉树中的深度
为了计算二叉树T中结点的深度，首先在改写的有向树T中形成一个欧拉回路。该回路对应于树的遍历过程，如图4(a)所示，它可以用一个连接树中所有结点的链表来表示。其结构如下：
- 如果结点的左子女存在，则结点的A处理器指向其左子女的A处理器，否则就指向自身的B处理器。
- 如果结点存在右子女，则结点的B处理器指向其右子女的A处理器，否则就指向其自身的C处理器。
- 如果一个结点是其父母结点的左子女，则结点的C处理器指向其父母的B处理器，如果该结点是其父母结点的右子女，则结点的C处理器指向其父母的C处理器。根结点的C处理器指向NIL。
因此，根据欧拉回路形成的链表的表头是根结点的A处理器，表尾是根节点的C处理器。如果已知构成原始树的指针，则我们可以在O(1)的时间内构造出欧拉回路。
在我们获得表示T的欧拉回路的链表后，我们在每个A处理器中放入值1，在每个B处理器中放入值0，在每个C处理器中放入值-1，如图4(a)所示。然后如第1.2节中那样，我们运用满足结合律的普通加法来执行并行前缀计算。图4(b)说明了并行前缀计算的结果。
我们说，在执行完并行前缀计算过程后，每个结点的深度值在结点的C处理器中。为什么呢？我们按以下要求把数放入A，B和C三个处理器中：访问子树的最后结果是把运行和加上0。每个结点i的A处理器对其左子女树的运行和加1，这表明i的左子女的深度比i的深度大1。B处理器对运行和没有影响，这是因为i的左子女的深度与其右子女的深度相等。C处理器使运行和减1，以便对i的父母结点来说，对以i为根结点的子树进行访问后运行和不会改变。
我们可以在O(1)的时间内计算出表示欧拉回路的列表。列表中包含3n个对象，所以执行并行前缀计算过程仅需O(lgn)的运行时间。因此，计算所有结点深度所花费的全部运行时间为O(lgn)。又因为算法执行中不需要对有存储器执行并发存取操作，所以该算法是一个EREW算法。
