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, 6Every 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?
I/O cost to traverse a tree stored in preorder form
algorithm analysis;data structures;binary trees;graph traversal
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:Read $B$ nodes into a buffer.For each node in the buffer:Push $(node.id, num\_children(node), 0)$ to stack $S$ (respectively $(id, num, d)$).While $S.peek().num = 0$:$d = S.peek().d$Output $(S.peek().id, d)$.$S.pop()$$S.peek().num = S.peek().num - 1$$S.peek().d = max(S.peek().d, d + 1)$.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$.