CSC 216/s08/make plans

Formatting Resources

Formatting Help Guide from MetaWiki

Understanding Traversal Types on Binary Trees

Binary Trees are a new concept and it is important to have a solid understanding of binary trees and how to traverse them before moving onto the concept of binary search trees.

The problem

You are given a stack of circles having either a letter or a number in the center of each. You have no knowledge of how to order them. The professor will hand out a list of numbers and a list of letters. Depending upon which stack type you are given, you must order them properly from the binary tree that will be written on the blackboard. The professor will tell you the traversal type. You have 2 minutes to do so.

Participants and props

There will be 4 groups of 3 at the front of the room. The activity is timed.

You will be given a stack of circles with velcro backing. Each group would also be given a blank board that the velcro would stick to. The idea is that the board can be raised to show the rest of the class what the student is thinking and what the guess is.

One stack will have a single letter on each circle. The letter stacks will be given to two of the four groups.

One stack will have a single number on each circle. The number stacks will be given to the remaining two groups.

The script

You are pitted against a classmate on the opposing team who also must order the same type of list you are (letters or numbers). The object is to order the given list of letters and numbers before the other team or before the 2 minutes have expired.

One of the three ways of traversal, Preorder Traversal, Inorder Traversal, and Postorder Traversal, will be spoken aloud. A binary tree will be written on the blackboard. You must order your the circles, in a row, as quickly as possible based on the traversal type stated. The exercise is repeated for the other two members of the group. The traversal type would change for each repetition. Times for each of the 3 runs are tallied, and the team winners get 1 bonus point on the next test.

The point of this exercise is not to be told what each of the 3 traversal types are. Mistakes and confusion are expected, and this is important because the exercise must be discussed with the class and each person can see if their guess on how to do it worked was correct or not. The idea is that while it might be self-evident, you may still be wrong in the concept of each of the three traversal types. By making egregious errors, and then discussing them afterwards, each of the types will be cemented into each of the student's mind.

The whole exercise should take no more than 15-20 minutes.

Example

For example, let's say you are given the tree

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

The proper Preorder traversal would be: 5, 3, 1, 2, 4, 8, 6, 7, 9

The proper Postorder traversal would be: 2, 1, 4, 3, 7, 6, 9, 8, 5

The proper Inorder traversal would be: 1, 2, 3, 4, 5, 6, 7, 8, 9