Description
In this assignment, you are required to implement binary search tree creation in C and Python
languages and compare the performance of your implementations.
In your C implementation, you are not allowed to use any struct or pointers to build your tree. You
should use the same data structures/tree format in your Python code.
The property that makes a binary tree into a binary search tree is that for every node, X, in the tree,
the values of all the keys in its left subtree are smaller than the key value in X, and the values of all
the keys in its right subtree are larger than the key value in X (More information in “Data Structures
and Algorithm Analysis in C, Mark A. Weiss, Addison Wesley”).
Your program should start by reading a set of integer values (separated by space) from a text file
into an array and build a binary search tree by using the values in the (unordered) array. After
building the tree, your program should save the binary search tree in a text file in sorted order (inorder traversal).
Your program should measure and report the execution time for building the tree. The measured
time should not include the I/O operations. Time measurement should be done in the following
order:
read the input file into an array // file read operation
start time
build tree // the operation we want to measure
stop time
print tree in the output file // file write operation
You can assume that the input file does not contain any duplicate values. You can limit the number
of nodes in your tree (by specifying the maximum number of nodes it can include). It should be
large enough to demonstrate the performance of the execution.
Requirements:
You are required to execute your programs written in C and Python for the same input files
by including (at least 3) cases with different number of integer values.
You are required to submit the source code and a report that includes implementation details,
performance results and explanations about the results by including possible reasons.
You need to work individually, no group work is allowed.
If you use any source code available on the web, give the reference in your report.
No late homework will be accepted.
Submission: You are required to submit your commented source code and report to LMS. Please
create a compressed file including all source files and report; and name it as
yourstudentnumber_P1.zip (e.g. If your student number is 202012345678, the file name must be
202012345678_P1.zip).
