How does a postorder traversal work, and why is it the right order for computing folder sizes?

Postorder visits a node after its descendants: recursively traverse each child's subtree, then visit the node. A folder's size is the sum of its contents' sizes, so it can only be computed once all its children are done.

* The files come first; each folder is visited only after everything in it, so it can add them up. *

Algorithm postOrder(v)
  for each child w of v
    postOrder(w)
  visit(v)

The visit happens post, after the recursive calls. So the leaves are visited first and the root last.

That order is what a folder-size computation needs. homeworks/ can report 5K only after both of its files (3K and 2K) have been visited; cs16/ can report its 61K only after homeworks/, programs/ and todo.txt all have. Any computation where a node's result depends on its children's results has this shape: deleting a directory tree, freeing memory, evaluating an expression.

Go deeper:

• du (Unix) — the disk-usage tool, a postorder traversal of the file system in practice.