Re: hacker challenge - traverse a list
- From: Julienne Walker <happyfrosty@xxxxxxxxxxx>
- Date: Fri, 29 Feb 2008 10:12:58 -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 notice you didn't mention that the structure of the tree can't
change, so why not rotate away the left branches as you traverse? Even
better, once you're done you can make a second pass that balances the
tree. ;-)
.
- Follow-Ups:
- Re: hacker challenge - traverse a list
- From: Andrey Tarasevich
- Re: hacker challenge - traverse a list
- References:
- hacker challenge - traverse a list
- From: Richard Harter
- 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
|
