Cheap and Secure Web Hosting Provider : See Now

# [Solved]: I/O cost to traverse a tree stored in preorder form

, ,
Problem Detail:

Let T be a binary tree that is stored in the disk following the preorder layout.

For example if this is $T$:

then $T$ will be stored in the disk as follows:

10, 11, 0, 12, 13, 2, 7, 3, 14, 1, 15, 16, 4, 8, 17, 18, 5, 9, 6

Every node of the tree is a struct that stores the offset of the left child, the offset of the right child, the id of the node and a size variable. If a node is a leaf the offsets are set to -1.

Suppose that now in every node $u \in T$ we want to know what is the size of the subtree rooted on $u$. Assume that the elements between the disk and the memory are transferred in blocks of size $B$, the size of the memory is $M$ and it holds that $M \geq B$. Is it possible to do that in $O(\frac{N}{B})$ I/Os?

It is possible to do it in $O(\frac{N}{B})$ if you have $B + D$ memory available, where $D$ is the maximum depth of the tree. Algorithm:

1. Read $B$ nodes into a buffer.
2. For each node in the buffer:
1. Push $(node.id, num\_children(node), 0)$ to stack $S$ (respectively $(id, num, d)$).
2. While $S.peek().num = 0$:
1. $d = S.peek().d$
2. Output $(S.peek().id, d)$.
3. $S.pop()$
4. $S.peek().num = S.peek().num - 1$
5. $S.peek().d = max(S.peek().d, d + 1)$.
3. If there are more nodes to process, go to 1.

The idea behind this algorithm is to associate pushing on the stack with going down a child node, and popping coming back up to a parent node.

If we initialize every node with a counter containing the number of child nodes, and we decrement this counter everytime after popping, it means that once the counter hits 0 we have visited every child node as we visit this node: we are in post-order.

We also store a maximum subtree size $d$ with every node. If we pop (go back to visit the parent node) we store the maximum of $node.d$ and $child\_node.d + 1$ into this node. This means that once we are in post-order we have the maximum size of all child subtrees + 1 stored in $d$.