How is an arithmetic expression tree evaluated, and why is that a postorder traversal?

Recursively: a leaf returns its number; an internal node first evaluates its left and right subtree, then applies its operator to the two results. The node is handled after its children — postorder. For $((2 × (5 − 1)) + (3 × 2))$ the result is 14.

* Values flow upwards: 5 − 1 = 4, then 2 × 4 = 8 and 3 × 2 = 6, and finally 8 + 6 = 14. *

Algorithm evalExpr(v)
  if isExternal(v)
    return v.element()
  else
    x ← evalExpr(leftChild(v))
    y ← evalExpr(rightChild(v))
    ◊ ← operator stored at v
    return x ◊ y

The order is forced by the arithmetic. An operator cannot be applied until both of its operands are known, and the operands are the values of its subtrees. So both subtrees must be finished first, which is precisely postorder: children, then node.

For the example: the leaves 5 and 1 give $5 - 1 = 4$; then $2 \times 4 = 8$; separately $3 \times 2 = 6$; finally the root computes $8 + 6 = 14$.

The same bottom-up pattern works for any value that is computed from the children's values, as with the folder sizes.

Go deeper:

• Reverse Polish notation — the postfix notation a postorder walk produces, and its stack-based evaluation.