ECE36800 Non-Programming Homework Exercise #5
Due Friday, February 26, 2021, 11:59pm (Submit through Gradescope)
IMPORTANT: Read and complete the following Academic Honesty Statement. Failure in
submitting a complete academic honest statement will result in a 0 for this homework.
“In signing this statement, I hereby certify that the work on this exercise is my own and
that I have not copied the work of any other student while completing it. I understand that,
if I fail to honor this agreement, I will be subject to disciplinary action as outlined in the
course policy.”
Printed Name:
login:
Signature:
I have discussed this homework with:
This homework covers learning objective 1: An understanding of basic data structures, including
stacks, queues, and trees; learning objective 2: An understanding of basic data structures,
including stacks, queues, and trees.
ECE36800 Purdue University 1
c Cheng-Kok Koh
1. The following functions construct a binary search tree from a sorted array.
1 typedef struct _Tnode {
2 int info ;
3 struct _Tnode * left ;
4 struct _Tnode * right ;
5 } Tnode ;
6
7 Tnode * Tnode_construct ( int info )
8 {
9 Tnode * node = malloc ( sizeof (* node ) ) ;
10 if ( node == NULL ) {
11 fprintf ( stderr , " can ’ t get memory \ n ") ;
12 return NULL ;
13 }
14 node -> info = info ;
15 node -> left = node - > right = NULL ;
16 return node ;
17 }
18
19 Tnode * BST_build ( int * array , int lb , int ub )
20 {
21 if ( lb > ub ) {
22 return NULL ;
23 }
24 int mid = ( lb + ub ) /2;
25 Tnode * node = Tnode_construct ( array [ mid ]) ;
26 if ( node == NULL ) {
27 return NULL ;
28 }
29 node - > left = BST_build ( array , lb , mid - 1) ;
30 node - > right = BST_build ( array , mid + 1 , ub ) ;
31 return node ;
32 }
Consider the statements in the main function:
33 int array [] = {1 , 3 , 5 , 7, 9 , 11 , 13 , 15};
34 int array_size = sizeof ( array ) / sizeof ( array [0]) ;
35 Tnode * bst = BST_build ( array , 0 , array_size - 1) ;
Draw the computation tree that corresponds to the function call BST build(array, 0, array size
- 1). You should show the last two parameters of the recursive function BST build in each node
of the computation tree.
Draw the binary search tree constructed.
ECE36800 Purdue University 2
c Cheng-Kok Koh
Ignoring the space required to store the array and the space to store the binary search tree, what
is the space complexity when array size is n? What is the time complexity when array size is
n? Justify your answers.
ECE36800 Purdue University 3
c Cheng-Kok Koh
2. This question is based on a question from Spring 2017 Exam 1. The following code fragment
defines a structure for storing a binary tree and a function for re-constructing a binary search tree
from an array of integers. The integers in the array are ordered according to the postorder traversal
of the original binary search tree. We also assume that all integers are distinct. Also assume that
all malloc calls are successful.
1 typedef struct _tnode {
2 int value ;
3 struct _tnode * left , * right ;
4 } tnode ;
5
6 tnode * build_bst_from_postorder ( int * array , int lb , int ub )
7 {
8 if ( lb > ub ) {
9 return NULL ;
10 }
11 tnode * node = malloc ( sizeof (* node ));
12 node -> value = array [ ub ];
13
14 // find the left subtree and the right subtree of node in the array
15 // assume that all integers in left subtree <= node -> value
16 int partition_idx = lb ;
17 while (( partition_idx < ub ) && ( array [ partition_idx ] <= array [ ub ])) {
18 partition_idx ++;
19 }
20 node -> left = build_bst_from_postorder ( array , lb , partition_idx -1);
21 node - > right = build_bst_from_postorder ( array , partition_idx , ub -1);
22 return node ;
23 }
(a) Instead of using a linear search to search for partition idx, replace lines 16–19 with an
iterative binary search to determine partition idx. Write down the pseudo-code for a suitable
replacement.
(b) Consider the replacement that you have made in (a). Let n be the number of integers in the array
passed to the function build bst from postorder. (i) What is the worst-case space complexity
for the re-construction of the entire binary search tree in terms of n using the big-O notation? (ii)
What is the best-case space complexity? Justify your answers. Your answers should not include
the space required for the input array and the re-constructed binary search tree.
(c) Consider the replacement that you have made in (a). Let n be the number of integers in the array
passed to the function build bst from postorder. (i) What is the worst-case time complexity
for the re-construction of the entire binary search tree in terms of n using the big-O notation? (ii)
What is the best-case time complexity? It is important to take into account the time complexity in
ECE36800 Purdue University 4
c Cheng-Kok Koh
executing lines 16–19 (the replaced version in (a)) of the function. Justify your answers.
ECE36800 Purdue University 5
c Cheng-Kok Koh
3. This question is based on a question from Spring 2019 Exam 2. The following code fragment
defines a structure for storing a binary tree and a function for re-constructing a binary search tree
(BST) from an array of integers. The integers in the array are ordered according to the preorder
traversal of the original BST. The array is called preorder in the function. Assume that all malloc
calls are successful.
typedef struct _Tnode {
int key ;
struct _Tnode * left ;
struct _Tnode * right ;
} Tnode ;
Tnode * Reconstruct_BST ( int * index , int * preorder , int size , int ub )
{
if (* index >= size )
return NULL ;
if ( preorder [* index ] > ub )
return NULL ;
Tnode * node = malloc ( sizeof (* node ));
node -> key = preorder [* index ];
* index += 1;
node -> left = Reconstruct_BST ( index , preorder , size , node -> key );
node -> right = Reconstruct_BST ( index , preorder , size , ub );
return node ;
}
(a) The following statements are in the main function.
int preorder [] = {16 , 12 , 10 , 14 , 20 , 18};
int index = 0; // initial position in preorder array
int size = sizeof ( preorder )/ sizeof ( preorder [0]); // array size
Tnode * root = Reconstruct_BST (& index , preorder , size , INT_MAX );
Draw the re-constructed BST. Note that INT MAX is the largest int possible. You may treat it
as ∞.
(b) Draw the computation tree that corresponds to the recursive calls of the function Reconstruct BST
in 3(a). The node that corresponds to the first call is shown below. The two terms in the node
correspond to *index and ub, where index and ub are parameters passed to the function. You
computation tree must show *index and ub in each node.
0, INT_MAX
*index, ub
(c) Let n be the number of integers in the preorder array passed to Reconstruct BST. (i) What
is the worst-case space complexity for the re-construction of the entire BST in terms of n using the
ECE36800 Purdue University 6
c Cheng-Kok Koh
big-O notation? (ii) What is the best-case space complexity? Justify your answers. Your answers
should not include the space required for the input array and the re-constructed BST.
(d) Let n be the number of integers in the preorder array passed to Reconstruct BST. (i) What
is the worst-case time complexity for the re-construction of the entire BST in terms of n using the
big-O notation? (ii) What is the best-case time complexity? Justify your answers.
ECE36800 Purdue University 7
c Cheng-Kok Koh
4. Consider the function Reconstruct BST in question 3. Write a version of that with the tail
recursion removed. We call the new version Reconstruct BST trr.
void Reconstruct_BST_trr ( int * index , int * preorder , int size ,
int ub , Tnode ** root )
{
}
ECE36800 Purdue University 8
c Cheng-Kok Koh