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.

(a) A Binary Tree that is "not" Height-Balanced

(b) A Binary Tree that is Height-Balanced

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

#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

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

treamNodeID]);

}

void setRightLink(int upstreamNodeID, int

downstreamNodeID){

arrayOfBTNodes[upstreamNodeID].setRightChildPtr(&arrayOfBTNodes[down

streamNodeID]);

}

void printLeafNodes(){

for (int id = 0; id

if

(arrayOfBTNodes[id].getLeftChildPtr() == 0 &&

arrayOfBTNodes[id].getRightChildPtr() == 0)

cout

}

cout

}

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

cin >> filename;

int numNodes;

cout

cin >> numNodes;

BinaryTree binaryTree(numNodes);

ifstream fileReader(filename);

if (!fileReader){

cout

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

if (binaryTree.checkHeightBalancedTree())

cout

else

cout

return 0;

}

Note that the height of a leaf node is 0 and the height of a non-existing tree (or sub tree) is -1. Node Height of Height of Abs. Height Left subtree Right subtree Diff. Balanced 2 YES NO NO YES YES YES 2 2 (a) A Binary Tree that is "not" Height-Balanced Node Height of Height of Abs. Height Left subtree Right subtree Diff. Balanced YES YES YES YES YES 2 4 (b) A Binary Tree that 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. Node Height of Height of Abs. Height Left subtree Right subtree Diff. Balanced 2 YES NO NO YES YES YES 2 2 (a) A Binary Tree that is "not" Height-Balanced Node Height of Height of Abs. Height Left subtree Right subtree Diff. Balanced YES YES YES YES YES 2 4 (b) A Binary Tree that is Height-Balanced