0

Suppose that we somehow get a dump of an alien computer's memory. Unfortunately, said alien civilization had much large RAM sizes than we have, and somehow loved functional languages so much that all the data is in a gigantic, unthreaded, binary search tree (with no parent pointers either). Hey, aliens have lots of stack for recursion!

Now this binary tree is in a gigantic 100 terabyte disk array. We need some way of getting an in-order traversal. There is the recursive way, which uses up stack, and no computer has 100 terabytes of stack, and also the "iterative" way, which is really manually maintaining a stack.

We are allowed to modify the tree, but only with additional pointer fields and integer fields at the nodes. This is because the 100 terabytes disk array is almost completely full. We definitely can't do something like use another 100 terabytes as mmap'ed stack or something.

How can this impossible task be completed? The really infuriating part is that, hey, the tree is sitting there, perfectly ordered, inside the disk array, but we can't seem to get it out in order.

ithisa
  • 752
  • 1
  • 8
  • 25
  • 1
    If the tree is balanced, you will only need a stack of size O(log(100TB) ~= CONST*7*40. The recursive traversal needs a stack linear with the *height* of the tree, and not number of nodes. – amit Dec 10 '13 at 20:04
  • Okay, 100 petabytes or something. Just assume the tree is small enough that we have the time to output all its contents, but big enough that the height blows the stack. – ithisa Dec 10 '13 at 20:09
  • 100PB will be ~CONST*7*50. The awesomeness of logarithm. The only real way you won't be able to have enough RAM for the height - and have a realistic (not bigger than number of atoms on earth) size, is if the tree is not balanced. A perfectly balanced tree of height 1000 has ~2^1001 nodes. This is (I think) more than the number of atoms in the universe... – amit Dec 10 '13 at 20:10
  • Suppose that we have only 16 registers, but need to traverse a large tree that completely fills memory. – ithisa Dec 10 '13 at 20:13
  • 1
    Well, in this case you need to iterate in O(1) space. [this thread](http://stackoverflow.com/q/791052/572670) discusses this question exactly. – amit Dec 10 '13 at 20:15

1 Answers1

1

You can traverse the tree, by temporarily linking the rightmost child in each tree to its successor in the inorder traversal. For example, when you first come to t:

     t
   / ^ \
  a  |  d
 /\  |
 b c-+

you link the rightmost element of the left child of t back to t via the originally null right child pointer. Later on when following right pointers, you come back to t and try to repeat the same procedure, but this time arriving back to t. In this case you restore the pointer to null, traverse t and continue traversing the right child of t.

This is essentially exercise 21 in "The Art of Computer Programming", Vol.1, section 2.3.1.

struct tree {
    tree (int v) : value (v), left (nullptr), right (nullptr) {}
    int value;
    tree *left, *right;
};

template<typename F>
void
inorder (tree *t, F visit) {
    while (t != nullptr) {
        if (t->left == nullptr) {
            visit (t);
            t = t->right;
        } else {
            tree *q, *r;
            r = t;
            q = t = t->left;
            while (q->right && q->right != r)
                q = q->right;
            if (q->right == nullptr)
                q->right = r;
            else {
                q->right = nullptr;
                visit (r);
                t = r->right;
            }            
        }
    }
}
chill
  • 16,470
  • 2
  • 40
  • 44