Re: hacker challenge - traverse a list

On 29 Feb 2008 20:25:55 GMT, Nelu <spamahead@xxxxxxxxx> wrote:

On Fri, 29 Feb 2008 17:56:24 +0000, 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.


What does in order mean? Inorder?


If you just want to print the content of every node no matter what the
order of the keys is, assign an index (number) to each node (even not
existing nodes) similar to what you would have in a heap structure.
You can use a loop to print each node by its index starting with 0 (the
root). To get to the node with a certain index you can constuct the path
step by step by diving the index (-1 if zero based) by 2 and using the
result to mark the parent and the remainder specifies how to reach the
current node from the parent node (0 means left, 1 means right).
This is expensive because you have to repeat some calculations to avoid
using a queue. What you probably need in this case is a cursor (pointer
to walk the tree), variables for the current node and target node indexes
and a flag that tells you if there were any nodes printed at this depth.
If none was printed you stop the algorithm as you just ran out of
nodes :).

The indexes are assigned starting with the root and from left to right at
each depth
0
1 2
3 4 5 6
and so on...


I assume this fits the O(1) description. (This is something I just made
up so it's not tested, I just assume it works). Each depth start with a
node of index 2^depth-1 (again, even if the node doesn't really exist).

Nice. IIANM the execution cost is O(n*h) where n is the number
of nodes and h is the maximum height - average case O(n*log(n))
and worst case O(n*n). Can this be improved to worst case
O(n*log(n))?



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
    ... order only using Oadditional memory. ... current node from the parent node ... variables for the current node and target node indexes ... The indexes are assigned starting with the root and from left to right at ...
    (comp.programming)
  • RE: *weird* overflow error *after* API call; call works OK, but later simple steps fail
    ... one service request before. ... We finally found out the root cause by using ... I think the memory address of qqq is overrided by some ... MSDN subscriber package) Our support engineer could help you isolate the ...
    (microsoft.public.vc.debugger)
  • Re: int main(void) { return main(); }
    ... Taking into account that I didn't even have root privileges...) ... Most modern operating systems that use memory protection are protected ... Decode email address using b64decode or uudecode -m ... strip view finger mount fcsk more fcsk yes spray umount sleep ...
    (comp.lang.c)
  • Re: strcpy giving sigsegv error
    ... the path that is taken to get to root. ... If you write on the memory of a quoted string literal, ... If you copy more than one character to path with strcpy(), ...
    (comp.unix.programmer)
  • Re: Corrupted IDE Flash storage
    ... the control panel applet is for the configuring the size object store. ... As your root is already mounted to external FS, it is really nothing about your storage. ... we use an IDE Flash memory mounted as root. ...
    (microsoft.public.windowsce.platbuilder)