Question

Using the following definition for a BST node:

class BTNode {
public:
  int data;
  BTNode *left;
  BTNode *right;
  BTNode(int d,BTNode *l=nullptr,BTNode *r=nullptr)
    :data(d),left(l),right(r)
  {}
};

Implement a function to calculate the balance factor of a node in a BST. The function prototype must match the following function:

int balance_factor(BTNode *subtree)
{
   // IMPLEMENT
   return -2;
}

You may implement other functions to help you. In particular, you may want to implement a function to calculate a node's height.

//C++

#include <iostream>
#include <fstream>
#include <random>

// DO NOT MODIFY BTNode
class BTNode {
public:
int data;
BTNode *left;
BTNode *right;
BTNode(int d,BTNode *l=nullptr,BTNode *r=nullptr)
:data(d),left(l),right(r)
{}
};

// DO NOT CHANGE FUNCTION PROTOTYPE
int balance_factor(BTNode *subtree)
{
// IMPLEMENT
return -2;
}

// DO NOT MODIFY ANY OF THE FUNCTIONS BELOW. THEY ARE USED FOR TESTING

void print_result(int bf)
{
std::cout << "Tree has balance factor = " << bf << "." << std::endl;
}

void print_feedback(int bf, std::ofstream &feedback)
{
feedback << "Tree has balance factor = " << bf << "." << std::endl;
}

int main()
{
BTNode *root = new BTNode(100,
new BTNode(25, new BTNode(0, nullptr, new BTNode(16))),
new BTNode(125,nullptr,new BTNode(2132)));
int ret = balance_factor(root)
print_result(ret);
return 0;
}

Answer 1

I have not modified your code i just implement balance factor function separatly. All you need to do is add the code in your program

int height(BTNode *subtree)
{
if(subtree==NULL)
return 0;
return 1+max(height(subtree->left),height(subtree->right));
  
}
int balance_factor(BTNode *subtree)
{
// IMPLEMENT
int leftheight;
int rightheight;
if(subtree==NULL)
return 1;
leftheight=height(subtree->left);
rightheight=height(subtree->right);
return abs(leftheight-rightheight);
return 0;
}

//extra height function is impleted as a helper for balance factor

//hope you like it! Have a good day ?