Traversal Sketching

We can also determine traversal sequences through a technique called

traversal sketching. To sketch a traversal, we first draw a horizontal line at the bottom of the tree. Then, we draw lines linking each node to this horizontal line.

For preorder traversal, the links are drawn from left to right, starting at the root:

For inorder traversal, the links are drawn from left to right:

And for postorder traversal, the links are drawn from right to left, starting at the root:

Another way to sketch a traveral sequence is tree contouring. The idea is that we draw a path along the tree's outline. For each of the traversal approaches, we place a tick on either the left, bottom, or right. Each time the countour crosses a tick, we record the ticked node.

With preorder traversal, the tick is placed on the lefthand side of the node:

With inorder traversal, the tick is drawn on the bottom of the node:

And with postorder traversal, the tick is drawn to the right of the node: