A LEVEL COMPUTING

Rev. Polish Notation

Theory

# 6. Binary tree and infix notation

The infix expression for this example is (6(4+5) - 25)/(2+3)

The algorithm used to traverse the binary tree in order to derive the infix expression is:

- Traverse the left branch until there is no left branch
- Visit the root of the current branch
- Traverse the right sub tree if there is one
- Repeat steps 1, 2 and 3 until every node has been visited.

This is called the **'inorder' 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 infix expression can be derived by following this algorithm. Use the NEXT button to see how the traversal happens.

**Challenge** see
if you can find out one extra fact on this topic that we haven't
already told you

Click on this link: in-order algorithm

Copyright © www.teach-ict.com