Re: hacker challenge - traverse a list

On Mar 3, 11:40 am, spinoza1111 <spinoza1...@xxxxxxxxx> wrote:
On Mar 1, 1:56 am, 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.

Thanks for submitting this very interesting challenge!

I am solving the problem (slowly as my schedule permits) without
hacking. I won't look at other solutions until I am done or give up.
This essay response describes my approach. Use of this approach or

In a nutshell: "don't hack: SIMULATE a stack".

The untested C sharp code that follows the essay is a stack simulator
which uses a single number to represent a stack with a fixed bound. It
is best viewed in a monospaced font.

It uses an old Fortran trick for representing arrays and stacks I used
in the very limited memory of IBM 1401 Fortran running on a minimal 8K
configuration, and learned in an old Cambridge University Press book
called, if memory serves, "Non-Numerical Programming in Fortran".
Decimal numbers are "squozed" into a large binary number by shifting
them by powers of ten.

It's not a hack and that's the beauty of the thing: using an object-
oriented language means that you can encapsulate your dirty laundry in
a class!

Right now, though, I am stuck on how to write inorder traversal with
my nice new stack. It is easy if you can use recursion, but we cannot.

I claim that using a stack simulated by a single integer gives
"order(1) prime" memory complexity and not O(1) because I view the
direct application of the big O notation to code as an error. Scoffers
may scoff and be damned, but given optimizing OO compilation, there is
no limit to inlining, and for this reason the essential cost of the
stack is (1) the cost of the integer that holds the stack and (2) the
code associated with the stack, which doesn't count.

I am looking forward to reading other replies because in the post tree
I see good people including Julienne and few of the thugs. Hey Randy
where is your solution, big man? But first I will spend some time
trying to do inorder traversal with a stack but without recursion.

Here is the untested code of the stack class, best viewed in a
monospaced font such as Courier New and implemented, in C Sharp, as a
struct.

private struct TYPintegerStack
{
uint INTstack;
byte BYTdecimalWidth;
ushort SHRshift;
public TYPintegerStack(byte bytWidth) // constructor
{
INTstack = 0;
BYTdecimalWidth = bytWidth;
SHRshift = (ushort)Math.Pow(10, BYTdecimalWidth);
}
public bool push(ushort shrValue)
{
if (shrValue >= Math.Pow(10, BYTdecimalWidth))
{
Console.WriteLine
("Value for push " +
shrValue.ToString() + " " +
"exceeds decimal width " +
BYTdecimalWidth.ToString());
return false;
}
long lngTest = INTstack * SHRshift + shrValue + 1;
if (lngTest > Math.Pow(2, 31) - 1)
{
Console.WriteLine("Stack overflow");
return false;
}
return true;
}
public ushort pop()
{
if (INTstack == 0)
{
Console.WriteLine("Stack underflow");
return 0;
}
ushort shrReturn =
(ushort)(INTstack % (int)SHRshift - 1);
INTstack /= SHRshift;
return shrReturn;
}
public bool Empty
{
get { return INTstack == 0; }
}
}

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

- Show quoted text -

The solution doesn't, I believe, even need a simulated stack.

Subsequent to the above post I found the following algorithm in
wikipedia for "threaded tree traversal inorder" with neither recursion
nor the stack but so far I haven't got its transliteration to C Sharp
to work and will try to do so. It is time for me to look at the rest
of the posts in this very interesting challenge, but I will continue
to work on this solution as well.

//while hasleftchild(node) do
// node = node.left
//do
// visit(node)
// if (hasrightchild(node)) then
// node = node.right
// while hasleftchild(node) do
// node = node.left
// else
// node = node.right
//while node ≠ null
.