# Tree Traversals

## Pre Order

Starting to the left of the root, draw an outline around the tree as shown in Figure 10. As you pass to the left of a node (where the red dot is marked) output the data in that node, i.e. DBACFEG

Algorithm

1. If tree empty do nothing

Otherwise

1. Visit the root (e.g. print the value of the data item at the root)
2. Traverse the left sub-tree in pre-order
3. Traverse the right sub-tree in pre-order

## In Order

Starting to the left of the root, draw an outline around the tree as shown in Figure 11. As you pass underneath a node (where the blue dot is marked) output the data in that node, i.e. ABCDEFG

Algorithm:

1. If tree empty do nothing

Otherwise:

1. Traverse the left sub-tree in in-order
2. Visit the root
3. Traverse the right sub-tree in in-order

## Post Order

Starting to the left of the root, draw an outline around the tree as shown in Figure 12. As you pass to the right of a node (where the green dot is marked) output the data in that node, i.e. ACBEGFD

Algorithm:

1. If tree empty do nothing

Otherwise:

1. Traverse the left sub-tree in post-order
2. Traverse the right sub-tree in post-order
3. Visit the root

## Infix / Polish / Reverse Polish

If you create a binary tree for any given expression:

Traversal Notation
Pre Order Polish
In Order Infix
Post Order Reverse Polish

For example:

pre-order will give:

+*AC/EG


In-order will give:

A*C+E/G (order of evaluation is (A*C) + (E/G))


Post-order will give:

AC*EG/+  (Reverse Polish form)