5. Binary tree and reverse Polish

The reverse Polish expression in this example is : 6 4 5 + * 25 - 2 3 + /

The algorithm to use to derive the reverse Polish expression is listed below

1. Traverse the left sub tree until there isn't one
2. Traverse the right sub tree (if there is one)
3. Re-visit the root of the current branch
4. Repeat 1,2,3 until every node has been visited.

This is called the 'postorder' algorithm. The algorithm is an example of recursion because it repeats the same set of actions at every node.

The flash movie below shows how the algebraic expression in reverse polish format can be derived by following this algorithm

It is possible to also derive the expression in reverse polish by using another algorithm called the preorder algorithm. This is

1. Visit the root node
2. Visit the left branch
3. Visit the right branch