Re: hacker challenge - traverse a list

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?

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

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).

--
Best regards,
Andrey Tarasevich
.

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)