hacker challenge - traverse a list


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.


Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
.

Relevant Pages

  • Re: hacker challenge - traverse a list
    ... in order only using Oadditional memory. ... We don't need no steenking rules! ... Use whatever language ... I notice you didn't mention that the structure of the tree can't ...
    (comp.programming)
  • Re: hacker challenge - traverse a list
    ... in order only using Oadditional memory. ... can't use recursion or simulate it with a stack. ...  We don't need no steenking rules! ...  Use whatever language ...
    (comp.programming)
  • Re: hacker challenge - traverse a list
    ... in order only using Oadditional memory. ... We don't need no steenking rules! ... Use whatever language ... I notice you didn't mention that the structure of the tree can't ...
    (comp.programming)
  • Re: How come Ada isnt more popular?
    ... I think the absence of manual memory management code actually furthers ... the rest of the language in such a way that GNAT didn't get it right ... fcuntional langauges you can do more against ressource leaks, ...
    (comp.lang.ada)
  • Re: Executable Memory in a Driver
    ... >> criminal to expose users to the added bluescreen and security risk. ... In a language that can't access outside an array, ... that doesn't need to move memory. ... > desired in the compiler. ...
    (microsoft.public.development.device.drivers)