Tree Traversals

Definition

If you're writing a program that uses trees, then you're likely to need to process the entire tree for some purpose at some point, typically looking at every node in the tree. To do so, you would logically start at the root of the tree and work your way down the branches. This process is what we call a Tree Traversal.

Every node a sub-tree

Consider for a moment our understanding of trees that, every node in a tree is the root of a Subtree. Therefor, any function that you write to process the entire tree could be used to process any sub-tree. This is the perfect recipe for a recursive algorithm to process trees.

Three options: Pre-order, In-order, & Post-order traversals

When you start to ask yourself how you're going to process your tree, you need to answer one question:

When do you process the data at the root node?

Pre-order Traversal

Pre-order means that the root is processed before its sub-trees.

In other words:

1. Process the root.
2. Process the left subtree with a recursive call.
3. Process the right subtree with a recursive call.

So if we wanted to print all the nodes in our tree with pre-order, then our code would look something like this:

template <class DataType>
void printPreorder(const TreeNode<DataType>* nodePtr) {
  if(nodePtr != NULL) {
    cout << nodePtr->getData() << endl;
    printPreorder(nodePtr->getLeft());
    printPreorder(nodePtr->getRight());
  }
}

In-order Traversal

In-order means that the root is processed between its sub-trees (for a binary tree).

In other words:

1. Process the left subtree with a recursive call.
2. Process the root.
3. Process the right subtree with a recursive call.

So if we wanted to print all the nodes in our tree with in-order, then our code would look something like this:

template <class DataType>
void printInorder(const TreeNode<DataType>* nodePtr) {
  if(nodePtr != NULL) {
    printInorder(nodePtr->getLeft());
    cout << nodePtr->getData() << endl;
    printInorder(nodePtr->getRight());
  }
}

Post-order Traversal

Post-order means that the root is processed after its sub-trees.

In other words:

1. Process the left subtree with a recursive call.
2. Process the right subtree with a recursive call.
3. Process the root.

So if we wanted to print all the nodes in our tree with post-order, then our code would look something like this:

template <class DataType>
void printPostorder(const TreeNode<DataType>* nodePtr) {
  if(nodePtr != NULL) {
    printPostorder(nodePtr->getLeft());
    printPostorder(nodePtr->getRight());
    cout << nodePtr->getData() << endl;
  }
}

Application

How will the output differ for each of the above print functions on the below tree?