CODEWITHSUNDEEP
algorithmtreebinary-treebinary-search-tree
ithisa
ithisa

Reputation: 780

In-order traversal of unthreaded binary search tree, without a stack

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.

Upvotes: 0

Views: 227

Answers (1)

chill
chill

Reputation: 16888

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;
            }            
        }
    }
}

Upvotes: 1

Related Questions