C++ PLEASE

Brute Force Approach:

A brute force approach to determine the closest integer to

a test integer would

be to scan through the array and determine the absolute valu

e of the difference between the test integer

and each of the integers in the array. We keep track of

the minimum absolute difference found so far and

the corresponding integer in the array. After scanning through

the entire array, we can print the

corresponding integer that has the minimum absolute differe

nce with the test integer.

Example for the Brute Force Approach

(test integer: 50)

Array

[23, 12, 78, 45, 56, 46, 33, 25]

Abs. Diff

27 38 28 5 6 4 17 25

with 50

Min. Abs

Diff with 50

27 27 27 5 5 4 4 4

Estimate of the

Closest Integer

23 23 23 45 45 46 46 46

Question 1:

What is the asymptotic time complexity (with respect t

o the number of comparisons) of the

brute force approach described above? Justify your answer.

Binary Search Tree-based Approach:

A binary search tree (BST)-based approach would be equiv

alent

to searching for the "test integer" in the BST. We start

the search process with the root node and proceed

to the left sub tree or right sub tree (and recursively there

after) depending on whether the test integer is

less than or greater than the node we are currently at.

For every internal node as well as a leaf node, if

any, that we come across during the search process, we

determine the absolute difference between the test

integer and the integer corresponding to the internal node or t

he leaf node, if any. We keep track of the

integer (in the BST) for which the absolute difference with

the test integer is the minimum and print the

same as the closest integer to the test integer at the

end of the search process. If the test integer is indeed

the value of an internal node (or a leaf node) during the sea

rch process, we simply return the test integer

itself as the closest integer and end the search process

.

Question 2:

What is the asymptotic time complexity (with respect t

o the number of comparisons) of the

BST-based approach? Justify your answer.

Question 3:

You are given the code to construct a BST of randomly gener

ated array of integers and

search for a "searchKey" using the getKeyIndex( ) function.

Your task is to develop the code for the

getClosestKey( ) member function (for the Binary Search T

ree class) implementing the above algorithm

to determine the closest integer in the BST to a testKe

y. You could refer to the getKeyIndex( ) function

to get an idea of how to search for a particular testKey

in the BST. Run the main function as it is, along

with the rest of the code (including the getClosestKey( ) fun

ction) and capture the screenshot obtained for

an array of 12 integers, maximum value for an integer is

99 and the test integer is 42. The screenshot should include a printout of the array generated and the closest integer to the test

integer entered by the user.

Question 4:

Draw a binary search tree for the 12-element array genera

ted to capture your screenshot for Question 3

and illustrate the execution of the algorithm with your tes

tKey as shown in the example below. For each

node visited in the BST, you should show the estimated values f

or the minimum absolute difference

between the testKey and the nodes in the BST as well as th

e estimated values for the closestKey.

Example for the BST-based Approach

(test integer: 50)

Submission

(through Canvas)

Submit a single word document that contains your answers fo

r questions 1, 2 and 4 as well as the

complete code for Question 3 along with a screenshot of the o

utput (as mentioned above).

#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[downs

treamNodeID]);

}

void setRightLink(int upstreamNodeID, int

downstreamNodeID){

arrayOfBTNodes[upstreamNodeID].setRightChildPtr(&arrayOfBTNodes[down

streamNodeID]);

}

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;

}

}

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;

}

int getKeyIndex(int searchKey){

int searchNodeID = rootNodeID;

while (searchNodeID != -1){

if (searchKey ==

arrayOfBTNodes[searchNodeID].getData())

return searchNodeID;

else if (searchKey <

arrayOfBTNodes[searchNodeID].getData())

searchNodeID =

arrayOfBTNodes[searchNodeID].getLeftChildID();

else

searchNodeID =

arrayOfBTNodes[searchNodeID].getRightChildID();

}

return -1;

}

int getClosestKey(int testKey){

int searchNodeID = rootNodeID;

// implement this function, starting to

compare/search

// from the rootNodeID

}

};

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);

int testKey;

cout << "Enter a test key: ";

cin >> testKey;

int closestKey = bsTree.getClosestKey(testKey);

cout << "Closest Key to " << testKey << " is: " << closestKey <<

endl;

return 0;

}