Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!jarthur!ucivax!eppstein
From: eppstein@wormwood.ics.uci.edu (David Eppstein)
Newsgroups: comp.theory
Subject: Re: what to call this kind of tree traversal
Message-ID: <27F8BF3D.17384@ics.uci.edu>
Date: 2 Apr 91 17:28:29 GMT
References: <1991Apr2.014125.21190@tss.com>
Reply-To: eppstein@ics.uci.edu (David Eppstein)
Organization: UC Irvine Department of ICS
Lines: 19
Nntp-Posting-Host: wormwood.ics.uci.edu

In article <1991Apr2.014125.21190@tss.com> yost@netcom.COM writes:
>Is there a standard name for a tree traversal that
>  * visits the node
>  * traverses the children, if any
>  * visits again
>Sort of a combination of preorder and postorder.

Especially in the context of parallel algorithms, this has typically
been called an "Euler tour".  If you turn each edge in the tree into two
edges, one directed each way, then the traversal really is an Euler tour
in the graph sense.

See R.E. Tarjan and U. Vishkin, "Finding biconnected components and
computing tree functions in logarithmic parallel time", 7th IEEE Symp.
Foundations of Computer Science (FOCS), 1984, pp. 12-20.

-d
--
David Eppstein    UC Irvine, Info & Computer Science    eppstein@ics.uci.edu