You are given the following code:(1) Code to construct a binary search tree using a sorted randomly generated array of integers (2) Code to determine the depth (level numbers) of the vertices in a binary tree Add a member function assignLevelNumbers( ) to the Binary Search Tree class to determine the level numbers of the vertices in a binary search tree (start Breadth First Search with the rootNodeID, which is considered to be at level 0) Add a member function getLevelNumber(int nodeid) in the Binary Search Tree class that in turn calls the getLevelNum( ) function on the BST node object corresponding to the 'nodeid' and returns the level number of node identified by its id. In the main function, first call the assignLevelNumbers( ) function on the object of class Binary Search Tree before determining the number of comparisons for successful search. Successful search: During the lecture, we saw that the number of comparisons for the successful search of a key in a binary search tree (BST) is one more than the level number of the vertex representing the key in the BST. In the main function, write a for loop that will go through the individual vertices and extract their level numbers using the getLevelNumber(int nodeid) function called on an object of the class Binary Search Tree. Use these level numbers of the vertices to calculate the average number of comparisons for a successful search and print the same. Test your code with the following values for the number of elements in the array. 10, 100, 1000, 10000 The maximum value for an element in each case is 2500. As part of the output, you need not print the contents of the array. Just print the average number of comparisons for a successful search for each of the above four values for the number of elements in the array. What to submit: Include both (a) and (b) in a single word document and submit:(a) The complete code for the binary search tree class (including the implementation of the assignLevelNumbers() and getLevelNumber(int) functions) and the associated classes as well as the extended main function that determines the average number of comparisons for a successful search.(b) Tabulate the values for the number of elements vs. the average number of comparisons for a successful search. Why is that the average number of comparisons increases very slowly with increase in the number of elements? Random input Array #include #include #include using namespace std; class BTNode{ private: int nodeid; int data; int levelNum; BTNode* leftChildPtr; BTNode* rightChildPtr; public: BTNode(){} void setNodeId(int id){ nodeid = id; } int getNodeId(){ return nodeid; } void setData(int d){ data = d; } int getData(){ return data; } void setLevelNum(int level){ levelNum = level; } int getLevelNum(){ return levelNum; } void setLeftChildPtr(BTNode* ptr){ leftChildPtr = ptr; } void setRightChildPtr(BTNode* ptr){ rightChildPtr = ptr; } BTNode* getLeftChildPtr(){ return leftChildPtr; } BTNode* getRightChildPtr(){ return rightChildPtr; } int getLeftChildID(){ if (leftChildPtr == 0) return -1; return leftChildPtr->getNodeId(); } int getRightChildID(){ if (rightChildPtr == 0) return -1; return rightChildPtr->getNodeId(); } }; class BinarySearchTree{ private: int numNodes; BTNode* arrayOfBTNodes; int rootNodeID; public: BinarySearchTree(int n){ numNodes = n; arrayOfBTNodes = new BTNode[numNodes]; for (int index = 0; index < numNodes; index++){ arrayOfBTNodes[index].setNodeId(index); arrayOfBTNodes[index].setLeftChildPtr(0); arrayOfBTNodes[index].setRightChildPtr(0); arrayOfBTNodes[index].setLevelNum(-1); } } void setLeftLink(int upstreamNodeID, int downstreamNodeID){ arrayOfBTNodes[upstreamNodeID].setLeftChildPtr(&arrayOfBTNodes[downstreamNodeID]); } void setRightLink(int upstreamNodeID, int downstreamNodeID){ arrayOfBTNodes[upstreamNodeID].setRightChildPtr(&arrayOfBTNodes[downstreamNodeID]); } void constructBSTree(int *array){ int leftIndex = 0; int rightIndex = numNodes-1; int middleIndex = (leftIndex + rightIndex)/2; rootNodeID = middleIndex; arrayOfBTNodes[middleIndex].setData(array[middleIndex]); ChainNodes(array, middleIndex, leftIndex, rightIndex); } void ChainNodes(int* array, int middleIndex, int leftIndex, int rightIndex){ if (leftIndex < middleIndex){ int rootIDLeftSubtree = (leftIndex + middleIndex-1)/2; setLeftLink(middleIndex, rootIDLeftSubtree); arrayOfBTNodes[rootIDLeftSubtree].setData(array[rootIDLeftSubtree]); ChainNodes(array, rootIDLeftSubtree, leftIndex, middleIndex-1); } if (rightIndex > middleIndex){ int rootIDRightSubtree = (rightIndex + middleIndex + 1)/2; setRightLink(middleIndex, rootIDRightSubtree); arrayOfBTNodes[rootIDRightSubtree].setData(array[rootIDRightSubtree]); ChainNodes(array, rootIDRightSubtree, middleIndex+1, rightIndex); } } void printLeafNodes(){ for (int id = 0; id < numNodes; id++){ if (arrayOfBTNodes[id].getLeftChildPtr() == 0 && arrayOfBTNodes[id].getRightChildPtr() == 0) cout << arrayOfBTNodes[id].getData() << " "; } cout << endl; } void InOrderTraversal(int nodeid){ if (nodeid == -1) return; InOrderTraversal(arrayOfBTNodes[nodeid].getLeftChildID()); cout << arrayOfBTNodes[nodeid].getData() << " "; InOrderTraversal(arrayOfBTNodes[nodeid].getRightChildID()); } void PrintInOrderTraversal(){ InOrderTraversal(rootNodeID); cout << endl; } }; void selectionSort(int *array, int arraySize){ for (int iterationNum = 0; iterationNum < arraySize-1; iterationNum++){ int minIndex = iterationNum; for (int j = iterationNum+1; j < arraySize; j++){ if (array[j] < array[minIndex]) minIndex = j; } // swap array[minIndex] with array[iterationNum] int temp = array[minIndex]; array[minIndex] = array[iterationNum]; array[iterationNum] = temp; } } int main(){ int numElements; cout << "Enter the number of elements: "; cin >> numElements; int *array = new int[numElements]; int maxValue; cout << "Enter the maximum value for an element: "; cin >> maxValue; srand(time(NULL)); cout << "array generated: "; for (int index = 0; index < numElements; index++){ array[index] = rand() % maxValue; cout << array[index] << " "; } cout << endl; selectionSort(array, numElements); BinarySearchTree bsTree(numElements); bsTree.constructBSTree(array); cout << "Inorder traversal: "; bsTree.PrintInOrderTraversal(); cout << "Leaf nodes: "; bsTree.printLeafNodes(); return 0; } Binary Tree Level Numbers #include #include #include #include // for string tokenizer and c-style string processing #include // max function using namespace std; class BTNode{ private: int nodeid; int data; int levelNum; BTNode* leftChildPtr; BTNode* rightChildPtr; public: BTNode(){} void setNodeId(int id){ nodeid = id; } int getNodeId(){ return nodeid; } void setData(int d){ data = d; } int getData(){ return data; } void setLevelNum(int level){ levelNum = level; } int getLevelNum(){ return levelNum; } void setLeftChildPtr(BTNode* ptr){ leftChildPtr = ptr; } void setRightChildPtr(BTNode* ptr){ rightChildPtr = ptr; } BTNode* getLeftChildPtr(){ return leftChildPtr; } BTNode* getRightChildPtr(){ return rightChildPtr; } int getLeftChildID(){ if (leftChildPtr == 0) return -1; return leftChildPtr->getNodeId(); } int getRightChildID(){ if (rightChildPtr == 0) return -1; return rightChildPtr->getNodeId(); } }; class Node{ private: int data; Node* nextNodePtr; Node* prevNodePtr; public: Node(){} void setData(int d){ data = d; } int getData(){ return data; } void setNextNodePtr(Node* nodePtr){ nextNodePtr = nodePtr; } Node* getNextNodePtr(){ return nextNodePtr; } void setPrevNodePtr(Node* nodePtr){ prevNodePtr = nodePtr; } Node* getPrevNodePtr(){ return prevNodePtr; } }; class Queue{ private: Node* headPtr; Node* tailPtr; public: Queue(){ headPtr = new Node(); tailPtr = new Node(); headPtr->setNextNodePtr(0); tailPtr->setPrevNodePtr(0); } Node* getHeadPtr(){ return headPtr; } Node* getTailPtr(){ return tailPtr; } bool isEmpty(){ if (headPtr->getNextNodePtr() == 0) return true; return false; } void enqueue(int data){ Node* newNodePtr = new Node(); newNodePtr->setData(data); newNodePtr->setNextNodePtr(0); Node* lastNodePtr = tailPtr->getPrevNodePtr(); if (lastNodePtr == 0){ headPtr->setNextNodePtr(newNodePtr); newNodePtr->setPrevNodePtr(0); } else{ lastNodePtr->setNextNodePtr(newNodePtr); newNodePtr->setPrevNodePtr(lastNodePtr); } tailPtr->setPrevNodePtr(newNodePtr); } int dequeue(){ Node* firstNodePtr = headPtr->getNextNodePtr(); Node* nextNodePtr = 0; int poppedData = -100000; //empty queue if (firstNodePtr != 0){ nextNodePtr = firstNodePtr->getNextNodePtr(); poppedData = firstNodePtr->getData(); } else return poppedData; if (nextNodePtr != 0){ nextNodePtr->setPrevNodePtr(0); headPtr->setNextNodePtr(nextNodePtr); } else{ headPtr->setNextNodePtr(0); tailPtr->setPrevNodePtr(0); } return poppedData; } int peek(){ Node* firstNodePtr = headPtr->getNextNodePtr(); if (firstNodePtr != 0) return firstNodePtr->getData(); else return -100000; //empty queue } }; class BinaryTree{ private: int numNodes; int rootNodeID; BTNode* arrayOfBTNodes; public: BinaryTree(int n){ numNodes = n; arrayOfBTNodes = new BTNode[numNodes]; rootNodeID = 0; for (int id = 0; id < numNodes; id++){ arrayOfBTNodes[id].setNodeId(id); arrayOfBTNodes[id].setLevelNum(-1); arrayOfBTNodes[id].setLeftChildPtr(0); arrayOfBTNodes[id].setRightChildPtr(0); } } void setLeftLink(int upstreamNodeID, int downstreamNodeID){ arrayOfBTNodes[upstreamNodeID].setLeftChildPtr(&arrayOfBTNodes[downstreamNodeID]); } void setRightLink(int upstreamNodeID, int downstreamNodeID){ arrayOfBTNodes[upstreamNodeID].setRightChildPtr(&arrayOfBTNodes[downstreamNodeID]); } void printLeafNodes(){ for (int id = 0; id < numNodes; id++){ if (arrayOfBTNodes[id].getLeftChildPtr() == 0 && arrayOfBTNodes[id].getRightChildPtr() == 0) cout << id << " "; } cout << endl; } bool isLeafNode(int nodeid){ if (arrayOfBTNodes[nodeid].getLeftChildPtr() == 0 && arrayOfBTNodes[nodeid].getRightChildPtr() == 0) return true; return false; } int getNodeHeight(int nodeid){ if (nodeid == -1 || isLeafNode(nodeid) ) return 0; int leftChildID = arrayOfBTNodes[nodeid].getLeftChildID(); // -1 if not exist int rightChildID = arrayOfBTNodes[nodeid].getRightChildID(); // -1 if not exist return max(getNodeHeight(leftChildID), getNodeHeight(rightChildID)) + 1; } int getTreeHeight(){ return getNodeHeight(0); } void assignLevelNumbers(){ Queue queue; queue.enqueue(rootNodeID); arrayOfBTNodes[rootNodeID].setLevelNum(0); while (!queue.isEmpty()){ int firstNodeInQueue = queue.dequeue(); int leftChildID = arrayOfBTNodes[firstNodeInQueue].getLeftChildID(); if (leftChildID != -1){ queue.enqueue(leftChildID); arrayOfBTNodes[leftChildID].setLevelNum(arrayOfBTNodes[firstNodeInQueue].getLevelNum()+1); } int rightChildID = arrayOfBTNodes[firstNodeInQueue].getRightChildID(); if (rightChildID != -1){ queue.enqueue(rightChildID); arrayOfBTNodes[rightChildID].setLevelNum(arrayOfBTNodes[firstNodeInQueue].getLevelNum()+1); } } } int getDepth(int nodeid){ return arrayOfBTNodes[nodeid].getLevelNum(); } }; int main(){ string filename; cout << "Enter a file name: "; cin >> filename; int numNodes; cout << "Enter number of nodes: "; cin >> numNodes; BinaryTree binaryTree(numNodes); ifstream fileReader(filename); if (!fileReader){ cout << "File cannot be opened!! "; return 0; } int numCharsPerLine = 10; char *line = new char[numCharsPerLine]; // '10' is the maximum number of characters per line fileReader.getline(line, numCharsPerLine, ' '); // ' ' is the delimiting character to stop reading the line while (fileReader){ char* cptr = strtok(line, ",: "); string upstreamNodeToken(cptr); int upstreamNodeID = stoi(upstreamNodeToken); cptr = strtok(NULL, ",: "); int childIndex = 0; // 0 for left child; 1 for right child while (cptr != 0){ string downstreamNodeToken(cptr); int downstreamNodeID = stoi(downstreamNodeToken); if (childIndex == 0 && downstreamNodeID != -1) binaryTree.setLeftLink(upstreamNodeID, downstreamNodeID); if (childIndex == 1 && downstreamNodeID != -1) binaryTree.setRightLink(upstreamNodeID, downstreamNodeID); cptr = strtok(NULL, ",: "); childIndex++; } fileReader.getline(line, numCharsPerLine, ' '); } binaryTree.assignLevelNumbers(); for (int id = 0; id < numNodes; id++) cout << "Depth of Node " << id << " : " << binaryTree.getDepth(id) << endl; return 0; }