In this project, you will determine whether a binary tree input by the user (in the form of an edge file, as

discussed in the slides/class) is height-balanced or not. A binary tree is said to be height-balanced if each internal node (including the root) in the tree is height-balanced. A node is said to be height-balanced if the absolute difference in the heights of its left sub tree and right sub tree is at most 1. The binary tree (a) below is not height-balanced (as nodes 1 and 2 are not balanced), whereas the binary tree (b) below is height-balanced. Note that the height of a leaf node is 0 and the height of a non-existing tree (or sub tree) is -1. You are given the code for the binary tree implementation discussed in class. You could first find the height of each node in the tree and then test for each internal node: whether the difference in the height of its left child and right child is at most 1. If this property is true for every internal node, then we exit the program by printing the binary tree is indeed height-balanced.

Come up with files for storing the edge information of the two binary trees (a) and (b), and demonstrate

the execution of your code to determine whether a tree is height-balanced or not.

Add any member variable (an array) to keep track of the height of the individual nodes in the tree as well

as use the information in this array to determine whether the binary tree is height-balanced or not.

Submission (through Canvas as a single word document):

(1) Complete code of the binary tree program, extended to determine if the tree is height-balanced or not.

(2) Screenshot of the outputs when the program is run for the above two binary trees (a) and (b).

C++ Code

#include

#include

#include

#include // for string tokenizer and c-style string processing

#include // max function

#include // to use abs 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 BinaryTree{

private:

int numNodes;

BTNode* arrayOfBTNodes;

public:

BinaryTree(int n){

numNodes = n;

arrayOfBTNodes = new BTNode[numNodes];

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)

return -1;

if (isLeafNode(nodeid) )

return 0;

int leftChildID = arrayOfBTNodes[nodeid].getLeftChildID(); // -1 if not exist

int rightChildID = arrayOfBTNodes[nodeid].getRightChildID(); // -1 if not exist

int heightOfLeftChild = getNodeHeight(leftChildID);

int heightOfRightChild = getNodeHeight(rightChildID);

return max(heightOfLeftChild, heightOfRightChild) + 1;

}

int getTreeHeight(){

return getNodeHeight(0);

}

bool checkHeightBalancedTree(){

// Implement this function to determine whether for each internal node, the absolute difference

// between the height of the left child and the right child is at most 1. If it is true for each internal ndoe, the

// binary tree is said to be height-balanced. Even if one internal node is not height-balanced, the

// whole binary tree is considered not height-balanced.

}

};

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

}

cout << "Tree Height: " << binaryTree.getTreeHeight() << endl;

if (binaryTree.checkHeightBalancedTree())

cout << "The tree is height balanced.." << endl;

else

cout << "The tree is not height balanced.." << endl;

return 0;

}