Question

Construct a Binary Search Tree (BST) program in C++. The program is required to:

1) load the BST from a dataset (I will provide the datasets-see below) in the order they exist in the dataset.

2) after the BST is built analyze the BST and display the following values:

2.1) the smallest branch height

2.2) the highest branch height

2.3) the number of nodes in the tree

2.4) the determination if the tree is balanced

2.5) the determination if the tree is complete

test file: 15

8

31

42

60

78

77

75

80

88

89

99

Answer 1

• Below is the C++ program for the BST insertion according to the given dataset in the txt file, and displaying many other information about the BST using many other functions.
• For better understanding of the code and all functionality please read the comments mentioned in every line and make sure that you keep you dataset in the same directory as that of your cpp(c++) file to get correct output.
• CODE:

//include all necessary headers.
#include <iostream>
#include <fstream>
using namespace std;

//structure of node of BST(binary search tree).
struct node
{
//data and left right pointers
   int data;
   node * left;
   node * right;
};

//function to create a new node of BST with given data
node *new_node(int data)
{
//create node with given data and set left right pointers to NULL and return node.
   node *temp = new node;
   temp->data = data;
   temp->left = temp->right = NULL;
   return temp;
}

//function to insert a node with given value in current BST with root given as root..
node* insert(struct node* node, int val)
{
   //if tree is empty, return new node with given value.
   if (node == NULL)
{
return new_node(val);
}

   //otherwise find correct position to insert this node down in the tree
   //if val is less than current node's data then recur in left of it
   if(val < node->data)
{
node->left = insert(node->left, val);
}
   else if(val > node->data)
{
node->right = insert(node->right, val);
}
   //return the node which is unchanged
   return node;
}
//function to calculate height of the BST.considering height of single node to be 1..
int height(node*root)
{
//if tree is empty then return 0
if(root==NULL)
{
return 0;
}
//otherwise return 1+ maximum height of left or right subtree.
return 1+max(height(root->left), height(root->right));
}

//function to check is the BST is balanced or not
bool is_balanced(node* root)
{
//if tree is empty then it is balanced.
if (root == NULL)
{
return true;
}

//calculate the height of the left and right subtree.
int l = height(root->left);
int r = height(root->right);

//if difference between height of left and right subtree is less than equal to 1 and left and right subtree is also height balanced then return true
if( abs(l - r) <= 1 && is_balanced(root->left)==true && is_balanced(root->right)==true)
{
return true;
}

//else return false
return 0;
}

//function to count and return the number of nodes int he given BST with root given
int count_nodes(node* root)
{
//if tree is empty return 0.
if (root==NULL)
{
return 0;
}
//otherwise return the count of nodes in left and right subtree +1 (for the current node)
return 1 + count_nodes(root->left) + count_nodes(root->right);
}

//function to check if the given BST is complete or not i.e, tree is full except the last level and all the leaf in last level are on left as possible.
bool is_complete ( node* root, int index,int total_nodes)
{
//if tree is empty then return true
if (root == NULL)
{
return true;
}

//if index of the current node is more than equal to the count of nodes then tree is not complete.
if (index >= total_nodes)
{
return false;
}

//if true for this node then check for left and right subtree and return the result.
return (is_complete(root->left, 2*index+1, total_nodes) && is_complete(root->right, 2*index+2, total_nodes));
}
//function to convert a string of integer to integer data type
int str_to_int(string &str)
{
//answer initialized to 0.
int ans=0;
//traverse string and add to answer considering number in base 10.
for(int i=0;i<str.size();i++)
{
ans=ans*10+(str[i]-'0');
}
//return answer.
return ans;
}
//to get minimum branch height starting from root to some leaf node.
int get_min(node*root)
{
//if empty tree then return 0.
if(root==NULL)
{
return 0;
}
//otherwise get minimum branch height of left and right subtree and add 1 for the current node.
return 1+min(get_min(root->left), get_min(root->right));
}
//driver function
int main()
{
//ifstream object to read a file containing dataset
ifstream Fp;
Fp.open("test.txt");
//string variable to read integer in each line
string str;
//root of the BST formed initialized to NULL i.e, initially empty.
node *root = NULL;

//read each line from file until EOF
while(getline(Fp, str))
{
//if root is NULL then this integer will be root node.
if(root==NULL)
{
//insert node with this value and make this node as root.
root=insert(root, str_to_int(str));
}
//otherwise insert it into BST with root.
else
{
insert(root, str_to_int(str));
}

}
//close file.
Fp.close();

//printing the values
cout<<"The smallest branch height is : "<<get_min(root)<<endl;
cout<<"The highest branch height is : "<<height(root)<<endl;

//call for counting node in the tree.
int counter=count_nodes(root);
cout<<"Number of nodes in the tree: "<<count_nodes(root)<<endl;

//call to check balancing of the tree
bool flag=is_balanced(root);
if(flag==true)
{
cout<<"Tree is balanced"<<endl;
}
else
{
cout<<"Tree is not balanced"<<endl;
}

   //check if tree is complete or not.
   flag=is_complete(root, 0, counter);
   if(flag==true)
{
cout<<"Tree is complete"<<endl;
}
else
{
cout<<"Tree is not complete"<<endl;
}

//return from main
return 0;
}

• INPUT:15
  8
  31
  42
  60
  78
  77
  75
  80
  88
  89
  99
• OUTPUT:The smallest branch height is : 2
  The highest branch height is : 9
  Number of nodes in the tree: 12
  Tree is not balanced
  Tree is not complete
• The BST looks like:

15 Root ग

• For better clarity as the code is a bit lengthy , the picture of the code and input/ouput is given below.

//include all necessary headers. #include <iostream> #include <fstream> using namespace std; // structure of node of BST (binary search tree). struct node //data and left right pointers int data; node * left; node * right; L ; //function to create a new node of BST with given data node *new_node (int data) // create node with given data and set left right pointers to NULL and return node. node *temp = new node; temp->data = data; temp->left = temp->right = NULL; return temp; //function to insert a node with given value in current BST with root given as root.. node* insert(struct node* node, int val) BL //if tree is empty, return new node with given value. if (node == NULL) { return new_node (val); //otherwise find correct position to insert this node down in the tree //if val is less than current node's data then recur in left of it if(val < node->data) node->left = insert (node->left, val);

node->left = insert (node->left, val); else if (val > node->data) node->right = insert (node->right, val); L //return the node which is unchanged return node; ] //function to calculate height of the BST.considering height of single node to be l.. int height (node root) //if tree is empty then return 0 if (root==NULL) return 0; //otherwise return l+ maximum height of left or right subtree. return 1+max (height (root->left), height (root->right)); 1/function to check is the BST is balanced or not bool is_balanced (node* root) { //if tree is empty then it is balanced. if (root == NULL) { return true; // calculate the height of the left and right subtree. int i = height (root->left); int r = height (root->right); //if difference between height of left and right subtree is less than equal to 1 and left and right subtree is also height balanced then return true if( abs (1 - r) <= 1 && is_balanced (root->left) ==true se is_balanced (root->right) ==true) return true;

return true; //else return false return 0; 7/function to count and return the number of nodes int he given BST with root given int count_nodes (node* root) //if tree is empty return 0. if (root==NULL) return 0; // otherwise return the count of nodes in left and right subtree +1 (for the current node) return 1 + count_nodes (root->left) + count_nodes (root->right); 7/function to check if the given BST is complete or not i.e, tree is full except the last level and all the leaf in last level are on left as possible. bool is_complete (node* root, int index, int total_nodes) { //if tree is empty then return true if (root == NULL) { return true; //if index of the current node is more than equal to the count of nodes then tree is not complete. if (index >= total_nodes) return false; //if true for this node then check for left and right subtree and return the result. return (is_complete (root->left, 2*index+l, total_nodes) && is complete (root->right, 2*index+2, total_nodes));

мно return (is_complete (root->left, 2*index+l, total_nodes) && is complete (root->right, 2*index+2, total_nodes)); L} //function to convert a string of integer to integer data type int str_to_int (string estr) i //answer initialized to 0. int ans=0; //traverse string and add to answer considering number in base 10. for(int i=0;i<str.size(); i++) ii мно со но с N N N ans=ans 10+(str[i]-'0'); //return answer. return ans; N N N N N N месо со но с N w w w //to get minimum branch height starting from root to some leaf node. int get_min(node root) { //if empty tree then return 0. if (root==NULL) return 0; w //otherwise get minimum branch height of left and right subtree and add 1 for the current node. return l+min (get_min (root->left), get_min (root->right)); w //driver function int main() w w w w мно со но с w Ian object to read a file containing dataset ifstream Fp; Fp.open("test.txt"); //string variable to read integer in each line string str; //root of the BST formed initialized to NULL i.e, initially empty. node *root = NULL; но с //read each line from file until EOF

//read each line from file until EOF while (getline (Ep, str)) //if root is NULL then this integer will be root node. if (root==NULL) le with this value and make this node as root. root-insert (root, str_to_int (str)); //otherwise insert it into BST with root. else insert (root, str_to_int (str)); //close file. Fp.close(); //printing the values cout<<"The smallest branch height is : "<<get_min(root) <<endl; cout<<"The highest branch height is : "<<height (root) <<endl; //call for counting node in the tree. int counter=count_nodes (root); cout<<"Number of nodes in the tree: "<<count_nodes (root) <<endl; // call to check balancing of the tree bool flagris_balanced (root); if (flag==true) cout<<"Tree is balanced"<<endl; CANON else cout<<"Tree is not balanced"<<endl;

cout<<"Tree is not balanced"<<endl; // check if tree is complete or not. flag=is_complete (root, 0, counter); if (flag==true) cout<<"Tree is complete"<<endl; opioioioioioioco 00 00 00 00 00 00 00 Join UNO CON else cout<<"Tree is not complete"<<endl; //return from main return 0; 198 199

Input/Output:

-ox test - Notepad File Edit Format 15 View Help (31

The smallest branch height is : 2 The highest branch height is : 9 Number of nodes in the tree: 12 Tree is not balanced Tree is not complete execution time : 5.778 s Process returned o (@xo_ Press any key to continue.

So if you have any doubt regarding this code and it's explanation please feel free to ask in the comment section and if it is helpful then please give an up vote to this solution, THANK YOU.