Tree Traversal

There are three further operations which could have been included in our specification for the binary tree, corresponding to the usual pre-order, in-order and post-order traversal of a binary tree. A traversal of a binary tree is an operation which accesses each node in the tree exactly once. As each node is encountered, it might be simply printed out or subject to some sort of processing. Each mode of traversal imposes an order in which the nodes are accessed.

For our example, the resulting sequence of values produced can be represented as a queue of natural numbers so that the range of such operations will be of sort queue. The enlarged data type for Binary-tree would thus import Queue and contain the three extra operations:

   pre-order  :  binary-tree  ->  queue

   in-order   :  binary-tree  ->  queue
 
   post-order :  binary-tree  ->  queue

together with the two extra axioms for each of the three new operations

$$\hbox{ {\tt in-order(empty) = new}}$$

$$\hbox{ {\tt in-order(make(l,n,r)) = join(add(in-order(l),n) , in-order(r))}}$$

$$\hbox{ {\tt post-order(empty) = new}}$$

$$\hbox{ {\tt post-order(make(l,n,r)) = join(post-order(l) , add(post-order(r),n))}}$$

$$\hbox{ {\tt pre-order(empty) = new}}$$

$$\hbox{ {\tt pre-order(make(l,n,r)) = join(join(add(new,n), pre-order(l)), pre-order(r))}}$$

The use of recursion produces very elegant axioms for these operations. Their form is easily understood with reference to the mode of traversal :

in-order    :          left     $\longrightarrow$ data element     $\longrightarrow$    right

post-order    :        left     $\longrightarrow$    right     $\longrightarrow$    data element

pre-order    :         data element     $\longrightarrow$    left     $\longrightarrow$    right

For in-order traversal, start at the root and first traverse each node's left branch, then the node and finally the node's right branch. This is a recursive process since each left and right branch is a tree in its own right. For example, with the tree of Exercise 9.6 above, in-order traversal produces the sequence of values 8 4 2 9 3 5.

For post-order traversal, start at the root and first access each node's left branch, then the node's right branch and finally the node itself. For the tree of Exercise 9.6, the corresponding sequence is 8 2 4 5 3 9.

In the case of pre-order traversal, start at the root and access the node itself, its left branch and finally its right branch. This leads to the sequence 9 4 8 2 3 5 for the tree of Exercise 9.6.

Note the more cumbersome form of the pre-order operation - this stems from the fact that the add operation for Queue places the element at the end of the queue, which means we can simply use the add operation to append the element to the left/right component for in-order/post-order traversal. However, for the case of pre-order traversal, in order to place the element at the front, we need first to create a queue containing the single element n, that is add(new,n).

Within the context of programming language execution, compilers utilise tree structures to obtain forms of an arithmetic expression which can be evaluated efficiently. The in-order traversal of the binary tree for an arithmetic expression produces the infix form of the expression, while the pre-order and post-order traversal lead to the prefix and postfix (reverse Polish) forms of the expression respectively. The advantage of reverse Polish notation is that arithmetic expressions can be represented in a way which can be simply read from left to right without the need for parentheses. For example, consider the expression a * (b + c). This expression can be represented by the binary tree

                         *
                        / \
                       a   +
                          / \
                         b   c

If we perform a post-order traversal in which we traverse the left branch of the tree, the right branch, followed by the node, we immediately recover the reverse Polish form of the expression, namely abc+*. This expression can then be evaluated using a stack. Starting from the left of the expression, each time an operand (one of the numerical values a, b or c in this example) is found, it is placed on the top of the stack. When an operator ( * or +) is read, the top two elements are removed form the stack and the appropriate operator applied to them and the result placed on the stack. When the complete expression has been evaluated, the stack will contain a single item which is the result of evaluating the expression.