Traversals in Practice

We now have four ways to traverse a tree, and each one makes a different task easy.

size and height are post-order: each computes a node’s answer only after it has its children’s answers. Any computation that builds a node’s result from its subtrees’ results works this way. If a tree stores an arithmetic expression, with operators at the internal nodes and numbers at the leaves, you evaluate it in post-order: compute the two operand subtrees first, then apply the operator at the node to their results.

Pre-order visits the node before either subtree, which is what you want when each node has to be handled before the things beneath it. To copy a tree, you must create a new node before you can attach its copied children to it, so you copy in pre-order. The same goes for saving a tree to a file so you can rebuild it later. If you write each node before its subtrees, whoever reads the file can create each parent before its children.

In-order visits the node between its two subtrees. On most of the trees we have drawn, it does not mean anything special. But binary search’s decision tree has its nodes arranged so that an in-order traversal produces their values in sorted order: 10 20 30 40 50 60 70 for the following example.

         40
    ┌─────┴─────┐
   20           60
 ┌──┴──┐     ┌──┴──┐
10     30   50     70

Level-order goes through the tree from top to bottom, so nodes closer to the root come first. When you want the node closest to the root that meets some condition, level-order reaches that node before it visits any deeper node. It does not spend time on deeper nodes you do not care about.