CMSC $315$ Data Structures and Algorithms

Programming Project $3$

The third programming project involves writing a program to read in the preorder representation

of a binary tree and determine whether it is a balanced binary search tree. Given the binary tree

shown below:

Its preorder representation would be $(53(28(11****)(41****)),(83(67****)**)).$ The

asterisks represent null children.

The program should repeatedly prompt the user for a binary tree. It should then display the tree

using indentation. For the above tree, its indented representation would be as follows:

$53$

$28$

$11$

$41$

$83$

$67$

It should then categorize the binary tree in one of three ways:

It is not a binary search tree

It is a balanced binary search tree

It is a binary search tree but it is not balanced

If the tree is not a balanced binary search tree, a binary search tree containing the same set of

values should be constructed and displayed in the indented format shown above. It is not

expected that the existing tree be rebalanced, just that a new tree with the same set of values be

constructed. Then the height of the original tree and the balanced binary search tree should be

displayed.

Shown below is a sample session that involves each of the above cases: