The rules for traversing a tree are, to visit all nodes of a tree you do this:
- Preorder: (1) visit the root node, then (2) visit all the nodes in the left subtree of the root, then (3) visit all the nodes in the right subtree of the root. In steps (2) and (3), use the same rule as above.
- Inorder: (1) visit all the nodes in the left subtree, (2) visit the root node, (3) visit all the nodes in the right subtree.
- Postorder: (1) visit all the nodes in the left subtree, (2) visit all the nodes in the right subtree, (3) visit the root.
For example, to do an inorder traversal of your tree,
- Visit the nodes, $(12, 25)$, in the left subtree.
- Visit the root, $31$.
- Visit the node in the right subtree, $(68,50,72,39,56,42,53,60)$
In step (1) we use the same rule: visit the left subtree of 12 (nothing there), then the root, 12, then the right subtree $(25)$. So now you've done task (1), having visited the nodes $12, 25$ in that order.
In step (2) we visit $(31)$, so now we've visited $12,25, 31$.
In step (3) we need to visit the nodes in the right subtree, using the rule Left-Root-Right, as we did before. It turns out that we'll visit the right subtree's nodes in order 39,42,50,53,56,60,72.
Doing this traversal by hand is complicated and prone to error. While computers are easily able to use these recursive rules, humans aren't so good at this. Fortunately, there's a three-step technique that's easy for people to apply.
- Draw an upward-pointing triangle around each node in your tree.
- "Shrink-wrap" the whole tree by drawing a closed circuit around the whole tree, making your circuit follow the tree as closely as possible, like this:
- Starting at the root node, trace the circuit counter-clockwise, listing a node as visited when: for a preorder traversal, you encounter the node for the first time (that is, when you travel along the left side of the node's triangle); for an inorder traversal, mark the node as visited when you encounter the node for the second time (that is, when you travel around the base of the node's triangle); for a postorder traversal, mark the node as visited when you encounter it for the last time (when you travel along the right side of the node's triangle).
Try it for your tree and each of the three traversals and you'll see what happens.