Traversals

One of the traits that comes with a tree is that it does not have a pre-determined logical ordering of the nodes, unless one is imposed from the outside.

For example, if we have the binary tree:

          A 
        /   \
      B       C

we could state that the nodes, printed in order, should be ABC, BAC, CAB, BCA, etc. All would be valid, depending on the criteria that we choose.

It is convenient to describe some of these ordering criteria in a reproducible way. This is similar to how we would describe the traversal of the list from head to tail, a queue from front to back, and a stack from top to bottom. For binary trees, we often consider three traversals: pre-order, in-order, and post-order.

For each of these traversals, there are essentially three operations:

• Visit the current node
• Traverse the left subtree
• Traverse the right subtree

Visiting the node means performing whatever operation we’re trying to do with each node. For example, if we are printing out the items stored in the nodes of the tree, then when we visit a node, we print out its item.

The order of these operations will determine whether we are doing an pre-order, in-order, or post-order traversal.

For the following examples, we will use the following tree:

              A
          /       \
      B               C
    /   \           /   \
  D      E        F      G

Pre-order Traversal

The order of the operations for a pre-order traversal is:

1. Visit the current node
2. Traverse the left subtree
3. Traverse the right subtree

The resulting pre-order traversal for the example tree is ABDECFG.

In-order Traversal

The order of the operations for an in-order traversal is:

1. Traverse the left subtree
2. Visit the current node
3. Traverse the right subtree

The resulting in-order traversal for the example tree is DBEAFCG.

Post-order

The order of the operations for a post-order traversal is:

1. Traverse the left subtree
2. Traverse the right subtree
3. Visit the current node

The resulting post-order traversal for the example tree is DEBFGCA.

Warmup Exercise

For this first warmup exercise, calculate the pre-order, in-order, and post-order traversals for the following tree:

              A
          /       \
      B               C
    /   \           /   \
  D      E        F      G
 / \    / \      / \    / \ 
H  I   J   K    L   M  N   O

Type up your traversals in a file called traversals.txt in your GitHub repository, and do not forget to add, commit, and push the file when you are done.