Re: hacker challenge - traverse a list
- From: Gene <gene.ressler@xxxxxxxxx>
- Date: Fri, 29 Feb 2008 18:30:14 -0800 (PST)
On Feb 29, 12:56 pm, c...@xxxxxxxx (Richard Harter) wrote:
Here is a little challenge - print the contents of a binary tree
in order only using O(1) additional memory. In other words you
can't use recursion or simulate it with a stack. As far as I
know you can't do this without some kind of hack. Also AFAIK
there is no way to do this that should ever be used in real code.
Rules? We don't need no steenking rules! Use whatever language
you like, though I suppose this is a natural for C based
languages. Tag bit solutions (i.e. mark a link as visited when
we go down it and unmark it when we come back up) don't count
because (a) everyone thinks of it, and (b) it (debatably) uses
O(log n) memory. Platform dependencies are okay - this a hack,
after all.
I think this was done 25 years ago:
G. Lindstrom. Scanning list structures without stacks or tag bits.
Information Processing
Letters, 2(2):47-51, June 1973.
Even if you use the classical Deutsch-Schorr-Waite algorithm, which
needs 2 tag bits per node, you can steal them from the low order bits
of the child pointers by insisting that nodes are allocated on 2-byte
boundaries, which most modern systems already do...
.
- Follow-Ups:
- Re: hacker challenge - traverse a list
- From: moi
- Re: hacker challenge - traverse a list
- From: CBFalconer
- Re: hacker challenge - traverse a list
- From: Richard Harter
- Re: hacker challenge - traverse a list
- From: Gene
- Re: hacker challenge - traverse a list
- Prev by Date: Re: hacker challenge - traverse a list
- Next by Date: Re: hacker challenge - traverse a list
- Previous by thread: Re: hacker challenge - traverse a list
- Next by thread: Re: hacker challenge - traverse a list
- Index(es):
Relevant Pages
|
