Tree Traversals

Overview

https://www.youtube.com/watch?v=4Tg0Fg6qzJY&index=2&list=PLCiOXwirraUB0HOYmEbmx-7KStKtoXZ6E

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)