I/O cost to traverse a tree stored in preorder form
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$.