Description
Question 1 – 15 points
(a) [5 points] What are the preorder, inorder, and postorder traversals of the binary tree
below:
M
O
L
A
G
H
R T
I
(b) [5 points] Insert 50, 40, 80, 30, 45, 70, 90, 10, 60, 75, 85 to an empty Binary Search Tree.
Show only the final tree after all insertions. Then delete 45, 40, 80, 75, 50 in given
order. Show only the final tree after all deletion operations. Use the exact algorithms shown in lectures. Verify your answers by using this visualization tool.
(c) [5 points] A binary search tree has a preorder traversal of P, F, B, M, K, S, R, Z. What
is its postorder traversal? Reconstruct the tree from those traversals and draw it.
Page 2
Fundamental Structures of Computer Science II
Question 2 – 70 points
(a) [30 points] Write a pointer-based implementation of Binary Search Tree named as
PbBST for maintaining a list of integer keys. Implement insert, deleteKey and
getHeight methods for PbBST class. Put your code into PbTreeNode.h, PbTreeNode.cpp,
PbBST.h and PbBST.cpp files. Prototypes of required methods:
void insert(int key); // 10 points
void deleteKey(int key); // 15 points
int getHeight(); // 5 points
(b) [10 points] Write another method for PbBST class to return the median of numbers in
that BST in linear time (linear in the number of items). Your method should have
the following prototype:
double medianOfBST();
(c) [15 points] Implement a method for PbBST class which prints the keys in a given range
(side by side) in O(log n + m) time, where n is the number of nodes in the tree and
m is the size of the range. You will not get any credit if your implementation runs
asymptotically slower. Your method should have the following prototype (assume
a < b):
void rangeSearch(int a, int b);
(d) [15 points] Height of BST is a very important property which affects the performance
of search, delete, and insert operations directly. In this part, you will analyze how the
height of BST changes as you insert and delete random number into/from the tree.
Write a global function, void heightAnalysis(); which does the following:
(1) Creates an array of 20000 random numbers and starts inserting them into an
empty BST. At each 1000 insertions, outputs the height of the tree.
(2) Shuffles the array created in part d1. Then iterates over it and deletes the numbers
from the tree. After each 1000 deletions, outputs the height of the tree.
Add your code to analysis.cpp file. When heightAnalysis function is called, it
needs to produce an output similar to the following one:
Page 3
Fundamental Structures of Computer Science II
Listing 2: Sample output
Part f - Analysis of BST height - part 1
-----------------------------------------
Tree Size Tree Height
-----------------------------------------
1000 x
2000 x
...
Part f - Analysis of BST height - part 2
-----------------------------------------
Tree Size Tree Height
-----------------------------------------
19000 x
18000 x
...
(e) [0 points] Create a main.cpp file which does the followings:
• creates an empty BST and inserts the following numbers into it: {40, 50, 45,
30, 60, 55, 20, 35, 10, 25}
• prints the height of the tree
• deletes 45 and 50 from the tree
• finds the median of numbers by using medianOfBST method
• prints numbers between 15 and 53 by using rangeSearch method
• calls heightAnalysis function
At the end, write a basic Makefile which compiles all your code and creates an executable file named hw2. Check out these tutorials for writing a simple make file:
tutorial 1, tutorial 2. Please make sure that your Makefile works properly on the
dijkstra server.
Question 3 – 15 points
After running your programs, you are expected to prepare a single page report 1 about the
experimental results that you obtained in Question 2 d. With the help of a spreadsheet
program (Microsoft Excel, Matlab or other tools), plot number of elements in tree versus
height of tree after each 1000 insertions and deletions. On the same figure, plot number
1Please make sure that your report does not exceed the specified page limit too much, otherwise you
may lose points
Page 4
Fundamental Structures of Computer Science II
of elements in tree versus theoretical average height of BST. A sample figure is given in
Figure 1 (these values do not reflect real values).
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2
x 104
0
5
10
15
20
25
Number of elements in tree
Tree height
Analysis of Average BST Height
After insertions
After deletions
Theoretical values
Figure 1: Sample figure
In your report, you need to discuss the following points:
• Do your findings related to average height of BST agree with the theoretical values?
State the theoretical value and discuss how close these values are to the values you
obtained.
• How would the height of the tree change if you inserted sorted numbers into it
instead of randomly generated numbers?
Page 5