Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!apple!usc!samsung!spool.mu.edu!uwm.edu!csd4.csd.uwm.edu!markh
From: markh@csd4.csd.uwm.edu (Mark William Hopkins)
Newsgroups: comp.theory
Subject: Non-recursive tree traversal (was: Re: tree traversal)
Keywords: non-recursive tree traversal algorithm needed
Message-ID: <9756@uwm.edu>
Date: 26 Feb 91 02:29:57 GMT
References: <anderson.667437145@mrcnext> <1991Feb25.074028.992@zorch.SF-Bay.ORG>
Sender: news@uwm.edu
Organization: University of Wisconsin - Milwaukee
Lines: 18

anderson@mrcnext.cso.uiuc.edu writes:
> I need _non-recursive_ pre, post and inorder tree traversal
> algorithms.
...
> Please, no algorithms which use "states" or a stack.

In article <1991Feb25.074028.992@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes:
>
>Well, you can't avoid saving _some_ state; you have to know at any node
>whether your are going up or down, for example, , but you can avoid
>saving O(log(N)) state; you can get by with O(1) state.

There is such an algorithm.  If you have 3 pointers on each tree-node (Left,
Right, Parent), then on each traversal of a node you rotate the pointers.

I think you also need the ability to compare nodes (for <, and >) too.

I have a version written in FORTRAN somewhere...


Brought to you by Super Global Mega Corp .com