Re: hacker challenge - traverse a list

On Fri, 29 Feb 2008 11:29:29 -0800, Andrey Tarasevich
<andreytarasevich@xxxxxxxxxxx> wrote:

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

What exactly is a "binary tree" in this case?

A tree with left and right child links only, no parent link;
traverse in the order specified by left and right.


In a tree that has child->parent links in addition to parent->child
links the solution is trivial. No hacks necessary.

True.

In a tree that only has parent->child links the the problem has no
solution with O(1) memory (the way you "defined" it in your "debatably"
part).

Not so. It depends upon what further restrictions you place.


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: B+ Tree and its concept
    ... I'm going from memory here (and experience with certain implementations ... b+ tree is a representation of the index ... no need to maintain the leaf level of the index separate from the data. ... there's a b-tree variant that always splits two nodes into three, ...
    (comp.databases.theory)
  • Re: [PATCH] add b+tree library
    ... btrees maintain the tree externally. ... So btrees have to allocate memory ... +struct btree_item { ...
    (Linux-Kernel)
  • Re: hacker challenge - traverse a list
    ... Your own contributions to this subject that I have read ... Is an array "one" memory element, ... question is a proportional relationship of memory use to size of tree ... But, Harter's question belongs to programming, and not to computer ...
    (comp.programming)
  • Re: [PATCH 4/4] add ksm kernel shared memory driver.
    ... Ksm works by walking over the memory pages of the applications it ... Ksm scan just memory areas that were registred to be scanned by it. ... +struct ksm_memory_region { ... * insert the pages into normal sorted tree and expect it to find anything. ...
    (Linux-Kernel)
  • Re: T Trees
    ... location when I arracng the tree in order of memory address. ... A memory allocator doesn't normally need to search for a block at ... The information about the blocks are its metadata. ...
    (comp.programming)