CS 202 Homework 2 – Binary Search Trees Solved

Question 1 – 20 points

    (a) (6 points) Give the prefix, infix, and postfix expressions obtained by preorder, inorder, and postorder traversals, respectively, for the expression tree below:











    (b) (9 points) I​nsert 31, 7, 56, 2, 1, 41, 45, 10, 70, 42, 38, 9 to an empty Binary Search Tree, and then delete 1, 45, 56, 7 in the given order. Show the evolution of the BST after each insertion and deletion operation.

    (c) (5 points) A binary search tree has a preorder traversal of 18, 5, 11, 9, 7, 13, 12, 15, 21, 19, 28, 23, 25, 24, 26. Give the corresponding binary search tree. What is its postorder traversal?



Question 2 – 65 points

You will write a pointer-based implementation of Binary Search Tree with various functions. Each node object will keep an integer data value together with left and right child pointers.

You are required to implement following functions:

bool​ ​isEmpty():​​Tests whether the BST is empty. True if BST is empty; otherwise false.
int getHeight():​Returns the height of the BST.

int getNumberOfNodes():​Returns the number of nodes in the BST.

bool add(const int newEntry): Adds a new node containing a given data item to the BST. If the data item already exists in the current BST, then don’t insert. Returns true if the addition is successful, or false if not.

bool remove(const int anEntry): ​Removes the node containing the given data item from BST. True if the removal is successful, or false if not.

bool contains(const int anEntry):​Tests whether the given data item occurs in the
BST. True if the BST contains the given data item, or false if not.

void preorderTraverse(): ​Traverses the BST in preorder and prints data item values in traversal order.

void inorderTraverse():​Traverses the BST in inorder and prints data item values in traversal order.

void postorderTraverse():​​Traverses the BST in postorder and prints data item values in traversal order.

void levelorderTraverse(): ​Traverses the BST in level-order and prints data item values in traversal order. A level-order traversal of a tree processes (visits) nodes one level at a time, from left to right, beginning with the root.


For this solution, if you need to use any additional data structure other than binary search trees, you should define and implement a class for that data structure. Note that you are allowed to use the C++ codes for any data structure such as ADT stack and ADT queue that are given in your textbook but are not allowed to use any other source implementation. For example, you cannot use the stack class defined in another book or on a web site. Similarly, you are not allowed to use any functions in the C++ standard template library (STL). You should upload this additional class as well as its header file in your solution.



int span(const int a, const int b):​Returns the number of nodes in the BST with data values within a specific range. In other words, it is the number of nodes with the data value >=a and <=b.

You should implement an efficient function -- that is, your function should not traverse any parts of the tree that it does not need to traverse. If you write a function that visits all nodes in the tree, you will get NO points from this question.



void mirror(): ​Changes the BST so that the roles of the left and right pointers are swapped at every node. When you apply this function to a BST, the data value in a node will be less than the data values in its left subtree and greater than the data values in its right subtree. If you apply this function to the mirrored tree, you should obtain the original BST.












    • Design the node structure together with its set and get functions (and maybe some additional functions if necessary) in ​BinaryNode.h ​and ​BinaryNode.cpp ​properly.

    • Implement the BST structure with above functions and their interfaces in

BinarySearchTree.h ​and ​BinarySearchTree.cpp ​properly. You are free to write helper functions to accomplish the tasks required from the above functions. ​Use the given file names and function signatures during implementation. ​You will not submit a main.cpp file, instead we will use our main.cpp file during evaluation. Therefore, it is important to use given file names and function signatures.


Question-3 – (15 Points)

Explain briefly how you implemented above ​levelorderTraverse​,​span ​and ​mirror ​functions and analyze their worst-case running time complexities. Give the time complexities. ​Discuss ​whether or not each can be implemented to be asymptotically faster.