# COMP 202: Principles of Object-Oriented Programming II

Tree Traversal Algorithms

## Mutable Binary Tree Framework

The Mutable Binary Tree Framework stores data in a hierarchical fashion, where mutation is allowed:

• Source code
• Documentation
• Key Design Patterns:
• The Composite Pattern: for implementing the structure
• The Visitor Pattern: for decoupling the algorithms on the structure from the structure itself
• The State Pattern: for implementing dynamic re-classification, allowing transparent state dependent behavioral changes.

## Tree Traversals

When we process a list, we basically have two ways to traverse it and move data along: forward (as in forward accumulation) or reverse (as in reverse accumulation).  In contrast, due to its non-linear structure, a binary tree can be traversed in many more different ways.  However, we can categorize data movement in two "directions": top-down and bottom-up.  In this lecture, we will study four tree traversal algorithms that are most common in tree processing.

1. In order traversal
2. Pre order traversal
3. Post order traversal

For the sake of definiteness, we consider the following trees as examples throughout:

mtTree: an empty tree

biTree: the non-empty tree

1
/     \
2         3
/    \          \
4      5           6
/
7

## In Order Traversal

Here is what it means to process a tree by traversing it in in order.

• For an empty tree:
• Do whatever is appropriate for the problem
• For a non-empty tree:
• Process the left subtree by traversing it in in order; (note the recursive definition here)
• Process the root; (the root is processed in between the processing of the left and right subtrees)
• Process the right subtree by traversing it in  in order; (not the recursive definition here)

Here is a concrete example of an in-order traversal of the above biTree.

### In class Exercise 1:

Write a visitor that prints the contents of a binary in in-order traversal.  What should the output be for the above biTree?

As you can see, there is so much similarity between the code for exercise 1 and InOrderAdd.  The question is whether or not we can separate the variants from the invariant and capture the abstraction of in-order traversal as the invariant.

Clearly, tree traversal is a visitor. What does it mean to "process the root"?  How can we enforce the order of processing?

Processing the root and each of the subtrees: use an abstract function ILambda; the concrete ILambdas are the variants.

Enforcing the order of processing: use the order in which the arguments of of a function are evaluated; this is the invariant.

So here is the invariant code for  in-order tree traversal.

## Post Order Traversal

Here is what it means to process a tree by traversing it in in order.

• For an empty tree:
• Do whatever is appropriate for the problem
• For a non-empty tree:
• Process the left subtree by traversing it in in order; (note the recursive definition here)
• Process the right subtree by traversing it in  in order; (not the recursive definition here)
• Process the root;  (the root is processed last, after processing the left and right subtrees).

### In class exercise 2:

Write an invariant post order traversal visitor analogous to the above in order traversal visitor.

## Pre Order Traversal

Here is what it means to process a tree by traversing it in in order.

• For an empty tree:
• Do whatever is appropriate for the problem
• For a non-empty tree:
• Process the root;  (the root is processed first, before processing the left and right subtrees).
• Process the left subtree by traversing it in in order; (note the recursive definition here)
• Process the right subtree by traversing it in  in order; (not the recursive definition here)

### In class exercise 2:

Write an invariant pre order traversal visitor analogous to the above in order traversal visitor.

Tree Traversal Algorithms

URL: http://www.clear.rice.edu/comp202/08-fall/lectures/tree/index.shtml