Re: hacker challenge - traverse a list

On Fri, 29 Feb 2008 13:13:55 -0800, Ben Pfaff
<blp@xxxxxxxxxxxxxxx> wrote:

cri@xxxxxxxx (Richard Harter) writes:

On Fri, 29 Feb 2008 10:04:26 -0800, Ben Pfaff
<blp@xxxxxxxxxxxxxxx> wrote:

cri@xxxxxxxx (Richard Harter) writes:

Here is a little challenge - print the contents of a binary tree
in order only using O(1) additional memory.

Do you want to limit runtime to O(n) or forbid modifying the
binary tree? I can think of a simple solution in the latter
category, and I have the sketch of a solution in the former
category.

Is it a binary search tree or an arbitrary binary tree?

What I was thinking of was a binary tree with left and right
children links and no parent links. Obviously it is trivial if
there is a parent link.

My take is that you can modify the tree during the traversal
provided that it is in the original condition when you are done.

One way to do it would be to use the BST rebalancing algorithm
described, among other places, at:
http://adtinfo.org/libavl.html/Balancing-a-BST.html
The first step of the algorithm converts the tree into a doubly
linked list. At this point, you can traverse it in inorder. The
second step balances the tree. The algorithm runs in O(1) space
and O(n) time.

This approach will not restore the original shape of the tree,
but the new shape is just as good or better than the original
shape for the purpose of typical BST operations. Perhaps it is
good for partial credit.

Works for me - I thought that's what you had in mind. If nobody
comes up with anything suitably dirty I'll post what I had in
mind.


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: database
    ... and Java. ... Binary trees have an elegant recursive pointer structure, ... Binary Tree Structure -- a quick introduction to binary ...
    (comp.lang.c)
  • Re: Answer to Dik T. Winter
    ... students (the "explanation" of the binary tree), ... "The state of Bavaria, situated in the south of Germany, is proud ... a complete infinite binary tree from that set of paths. ...
    (sci.logic)
  • Re: Answer to Dik T. Winter
    ... students (the "explanation" of the binary tree), ... Germany to get professorships – not by officially stated and discussed ... a complete infinite binary tree from that set of paths. ...
    (sci.logic)
  • Re: Cantor and the binary tree
    ... to do with paths on a tree, ... > nothing to do with the number of unending paths. ... Actually, if you have an infinite binary tree, with all paths unending, it's ...
    (sci.math)
  • Re: Cantor and the binary tree
    ... Rather, each one leads to another (unending, infinite) subtree. ... But for this new tree and each of its nodes the ... And if the binary tree is maximal as described, for each natural, there ... Given any maximal path in this maximal binary tree, ...
    (sci.math)