Real world pre/post-order tree traversal examples

Question

I understand pre-order, in-order, and post-order tree traversal algorithms just fine. (Reference). I understand a few uses: in-order for traversing binary search trees in order, pre-order for cloning a tree. But I can't for the life of me come up with a real world task that I'd need post-order traversal to accomplish.

Can you give me an example? And: can you give me any better uses for pre-order traversal?

Edit: Can anyone give me an example other than expression trees and RPN? Is that really all post-order is good for?

Answer 1

Post order is (can be) used by compilers. Consider an expression tree for a + b + c, the machine language would require a sequence like a b + c +. This is also called Reverse polish Notation (RPN). On the Wikipedia page it says: "RPN aka Postfix"

Post-order is required for destroying a tree, just like pre-order is needed to create/clone it.

Answer 2

As Henk Holterman pointed out, destroying a tree using manual memory management usually is a post-order traversal.

Pseudocode:

destroy(node) {
  if (node == null) return;

  destroy(node.left)
  destroy(node.right)

  // Post-order freeing of current node
  free(node)
}

Answer 3

Topological sorting is a post-order traversal of trees (or directed acyclic graphs).

The idea is that the nodes of the graph represent tasks and an edge from A to B indicates that A has to be performed before B. A topological sort will arrange these tasks in a sequence such that all the dependencies of a task appear earlier than the task itself. Any build system like UNIX make has to implement this algorithm.

The example that Dario mentioned — destroying all nodes of a tree with manual memory management — is an instance of this problem. After all, the task of destroying a node depends on the destruction of its children.