#include <iostream> #include <stdlib.h> #include <time.h> using namespace std; c
ID: 3706749 • Letter: #
Question
#include <iostream> #include <stdlib.h> #include <time.h> 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; } int findLCA(int leftSearchNodeData, int rightSearchNodeData){ // Implement the function here... } };
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] = 1 + rand() % maxValue; cout << array[index] << " "; } cout << endl; selectionSort(array, numElements); BinarySearchTree bsTree(numElements); bsTree.constructBSTree(array); cout << "Inorder traversal: "; bsTree.PrintInOrderTraversal(); cout << endl; for (int trials = 1; trials <= 4; trials++){
cout << "Trial " << trials << endl; int dataNodeA; cout << "Enter a data value for node A : "; cin >> dataNodeA; int dataNodeB; cout << "Enter a data value for node B : "; cin >> dataNodeB; int leftSearchNodeData = dataNodeA; int rightSearchNodeData = dataNodeB; if (dataNodeA > dataNodeB){ leftSearchNodeData = dataNodeB; rightSearchNodeData = dataNodeA; } cout << "LCA for " << leftSearchNodeData << " and " << rightSearchNodeData << " is " << bsTree.findLCA(leftSearchNodeData, rightSearchNodeData) << endl; cout << endl; }// trials return 0; } #include <iostream> #include <stdlib.h> #include <time.h> 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; } int findLCA(int leftSearchNodeData, int rightSearchNodeData){ // Implement the function here... } };
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] = 1 + rand() % maxValue; cout << array[index] << " "; } cout << endl; selectionSort(array, numElements); BinarySearchTree bsTree(numElements); bsTree.constructBSTree(array); cout << "Inorder traversal: "; bsTree.PrintInOrderTraversal(); cout << endl; for (int trials = 1; trials <= 4; trials++){
cout << "Trial " << trials << endl; int dataNodeA; cout << "Enter a data value for node A : "; cin >> dataNodeA; int dataNodeB; cout << "Enter a data value for node B : "; cin >> dataNodeB; int leftSearchNodeData = dataNodeA; int rightSearchNodeData = dataNodeB; if (dataNodeA > dataNodeB){ leftSearchNodeData = dataNodeB; rightSearchNodeData = dataNodeA; } cout << "LCA for " << leftSearchNodeData << " and " << rightSearchNodeData << " is " << bsTree.findLCA(leftSearchNodeData, rightSearchNodeData) << endl; cout << endl; }// trials return 0; } The lowest common ancestor (LCA) for two nodes A and B in a binary search tree (BST) is the node that is the common ancestor for both A and B, and is the farthest away from the root node of the BST. Note that depending on the BST, one of the two nodes A and B could themselves be the LCA of the other node or a third node (that is different from nodes A and B) could be the LCA. The three cases are illustrated in the following figure: 21 21 21 18 78 18 78 18 78 25) (81 25 81 25 81 1224 34 122434 122434 23 23 23 Node '6' with data 25 is the LCA for nodes 4' and'7" with data 23 and 34 respectively Case (a) Node '6 with data 25 is the LCA for nodes 4 and '6' with data 23 and 25 respectively Node '3' with data 21 is the LCA for nodes 3' and 9' with data 21 and 81 respectively Case (b) Case (c) Figure 1 In this quiz, you ll construct a BST based on a randomly generated and sorted array of integers, input the values (i.e., data) for two nodes A and B (that are part of the BST) and find the data corresponding to their LCA. Follow the steps below (1) You wll first construct a BST using a randomly generated and sorted array (sorted using Selection sort). The code to construct such a BST is given to you. (2) You will then input the data/values for the two search nodes A and B. Between the two nodes, determine the node whose data is relatively lower and call such a node as the leftSearchNode the other node will be then called the rightSearchNode. (3) The third and the major step is to initiate a search process starting from the root node (called say, the prospectiveAncestorNode - If the data for the leftSearchNode and rightSearchNode are both lower than that of the prospectiveAncestorNode, then the two nodes should be located in the left sub tree of the prospectiveAncestorNode. Hence, we set the id of the prospective ancestor node to correspond to the id of its left child and continue the search process in its left sub tree. -If the data for the leftSearchNode and rightSearchNode are both greater than that of the prospectiveAncestorNode, then the two nodes should be in the right sub tree of the
Explanation / Answer
#include <iostream>
#include <stdlib.h>
#include <time.h>
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;
}
int findLCA(int leftSearchNodeData, int rightSearchNodeData){
// Implement the function here...
}
};
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] = 1 + rand() % maxValue;
cout << array[index] << " ";
}
cout << endl;
selectionSort(array, numElements);
BinarySearchTree bsTree(numElements);
bsTree.constructBSTree(array);
cout << "Inorder traversal: ";
bsTree.PrintInOrderTraversal();
cout << endl;
for (int trials = 1; trials <= 4; trials++){
cout << "Trial " << trials << endl;
int dataNodeA;
cout << "Enter a data value for node A : ";
cin >> dataNodeA;
int dataNodeB;
cout << "Enter a data value for node B : ";
cin >> dataNodeB;
int leftSearchNodeData = dataNodeA;
int rightSearchNodeData = dataNodeB;
if (dataNodeA > dataNodeB){
leftSearchNodeData = dataNodeB;
rightSearchNodeData = dataNodeA;
}
cout << "LCA for " << leftSearchNodeData << " and " << rightSearchNodeData << " is " << bsTree.findLCA(leftSearchNodeData, rightSearchNodeData) << endl;
cout << endl;
}// trials
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.