Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!wuarchive!zaphod.mps.ohio-state.edu!ncar!noao!arizona!robert
From: robert@cs.arizona.edu (Robert J. Drabek)
Newsgroups: comp.edu
Subject: Re: Recursion?
Summary: answer
Message-ID: <26196@megaron.cs.arizona.edu>
Date: 9 Oct 90 18:39:51 GMT
References: <1990Oct5.101354.593@contact.uucp> <1990Oct7.015406.4948@water.waterloo.edu>
Distribution: na
Organization: U of Arizona CS Dept, Tucson
Lines: 18

Naji Mouawad writes:
> Speaking of recursion, here's a little thing to ponder ...
> 
> Traversing an ordered binary tree recursively is easy (Depth first say)
> Doing the same job using a stack is equally easy (takes more time to
> write down).
> How's about traversing a tree with a constant number of pointers ?
> 

Threaded trees.  They can even be written without the extra flag.
See Information Processing Letters, Vol 26, Number 4, 8 Nov. 1986:
Eliminating the flag in threaded binary sort trees; Dan Gordon.

-- 
Robert J. Drabek                            robert@cs.Arizona.EDU
Department of Computer Science              uunet!arizona!robert
The University of Arizona                   602 621 4326
Tucson, AZ  85721