CSC1020 Homework 9

Overview

In this homework you will practice recursively traversing a binary tree. You will implement preorder, postorder, and inorder traversals, then use a similar recursive approach to determine the height of the tree.

A partial BinaryTree<E> implementation is provided. Your work is limited to the four methods described below. You may create private helper methods as needed.

All four methods should use recursion to process the tree.

Requirements

1. Preorder Traversal

Write:

public String preOrder()

that returns the values in the tree using preorder traversal:

1. Visit the current node.
2. Traverse the left subtree.
3. Traverse the right subtree.

The returned String must:

• omit null values;
• contain exactly one space between node values;
• contain no leading or trailing spaces;
• return an empty String for an empty tree.

2. Postorder Traversal

Write:

public String postOrder()

that returns the values in the tree using postorder traversal:

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the current node.

The returned String must:

• omit null values;
• contain exactly one space between node values;
• contain no leading or trailing spaces;
• return an empty String for an empty tree.

3. Inorder Traversal

Write:

public String inOrder()

that returns a fully parenthesized inorder representation of the tree.

For each non-empty subtree:

1. place a left parenthesis before the subtree;
2. recursively process the left subtree;
3. add the value stored in the current node;
4. recursively process the right subtree;
5. place a right parenthesis after the subtree.

For a leaf node, the value appears directly inside the parentheses.

For a non-leaf node, place one space before and after the value stored in that node.

An empty subtree contributes nothing to the returned String.

For example, the following expression tree:

produces:

(((x) + (y)) * ((a) / (b)))

4. Height

Write:

public int height()

that returns the height of the tree.

For this assignment, height is the number of levels in the tree:

• an empty tree has height 0;
• a tree containing only the root has height 1;
• a tree whose deepest node is on the third level has height 3.

Complete Sample

Using the tree shown above:

        *
       / \
      +   /
     / \ / \
    x  y a  b

your methods should return:

preOrder():  * + x y / a b
postOrder(): x y + a b / *
inOrder():   (((x) + (y)) * ((a) / (b)))
height():    3

Use this example to check that you understand the order in which each traversal visits the nodes.

Testing

A JUnit test suite is provided to verify the required behavior. The supplied tests are not intended to cover every possible tree shape, so you are encouraged to add your own tests while developing your solution.

Useful cases to consider include:

• an empty tree;
• a tree containing only one node;
• a tree with only a left or right subtree;
• a tree with several levels;
• the sample expression tree shown above.

Your implementation should work for any BinaryTree<E>, not only the sample tree.