Re: hacker challenge - traverse a list

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.
The challenge isn't explicit so I suppose that revising the tree
counts.

O(n) is more elegant (!!?) and is what I had in mind, but a more
expensive method without modifying the tree is a fair solution.


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)