Answer the question below in C programming language by using…

QuestionAnswered step-by-stepAnswer the question below in C programming language by using…Answer the question below in C programming language by using concepts of tree and source code given. Image transcription textWrite a function boo] BSTzzdeepestNodeSOin BST class that ?nds and prints all the nodes at the deepestlevel. For example, the deepest nodes of treel in Figure 3.2 are 2, 7 and 12 while tree2 has only 21. (Hint: Youcan either use height of tree to look for deepest). Function will return false for empty tree and tru… Show moreSource Code:  BST.cpp#include #include #include #include “BST.h”  using namespace std;  BST::BST() {       root = NULL;       count = 0;}  bool BST::empty() {       if (count == 0) return true;       return false;}  int BST::size() {       return count;}  void BST::preOrderPrint() {       if (root == NULL) return;// special case       else preOrderPrint2(root);//normal process       cout << endl;}  void BST::preOrderPrint2(BTNode *cur) {       if (cur == NULL) return;       cur->item.print(cout);       preOrderPrint2(cur->left);       preOrderPrint2(cur->right);}  void BST::inOrderPrint() {       if (root == NULL) return;// special case       else inOrderPrint2(root);// normal process       cout << endl;}  void BST::inOrderPrint2(BTNode *cur) {       if (cur == NULL) return;       inOrderPrint2(cur->left);       cur->item.print(cout);       inOrderPrint2(cur->right);}  void BST::postOrderPrint() {       if (root == NULL) return;       else postOrderPrint2(root);       cout << endl;}  void BST::postOrderPrint2(BTNode *cur) {       if (cur == NULL) return;       postOrderPrint2(cur->left);       postOrderPrint2(cur->right);       cur->item.print(cout);}   int BST::countNode() {       int    counter = 0;       if (root == NULL) return 0;       countNode2(root, counter);       return counter;}  void BST::countNode2(BTNode *cur, int &count) {       if (cur == NULL) return;       countNode2(cur->left, count);       countNode2(cur->right, count);       count++;}  bool BST::findGrandsons(type grandFather) {       if (root == NULL) return false;       return (fGS2(grandFather, root));}  bool BST::fGS2(type grandFather, BTNode *cur) {       if (cur == NULL) return false;       //if (cur->item == grandFather) {       if (cur->item.compare2(grandFather)){               fGS3(cur, 0);//to find grandsons              return true;       }       if (fGS2(grandFather, cur->left)) return true;       return fGS2(grandFather, cur->right);}  void BST::fGS3(BTNode *cur, int level) {       if (cur == NULL) return;       if (level == 2) {              cur->item.print(cout);              return;        }       fGS3(cur->left, level + 1);       fGS3(cur->right, level + 1);}   void BST::topDownLevelTraversal() {       BTNode               *cur;       Queue             q;         if (empty()) return; // special case       q.enqueue(root);//enqueue the first node       while (!q.empty()) { // do 2 operations inside              q.dequeue(cur);              if (cur != NULL) {                      cur->item.print(cout);                      if (cur->left != NULL)                             q.enqueue(cur->left);                       if (cur->right != NULL)                             q.enqueue(cur->right);              }       }} //insert for BSTbool BST::insert(type newItem) {       BTNode *cur = new BTNode(newItem);       if (!cur) return false;            // special case 1       if (root == NULL) {              root = cur;              count++;              return true;                // special case 2       }       insert2(root, cur);                // normal       count++;       return true;}  void BST::insert2(BTNode *cur, BTNode *newNode) {       //if (cur->item > newNode->item) {       if (cur->item.compare1(newNode->item)){              if (cur->left == NULL)                      cur->left = newNode;              else                      insert2(cur->left, newNode);       }       else {              if (cur->right == NULL)                      cur->right = newNode;              else                      insert2(cur->right, newNode);       }}   bool BST::remove(type item) {       if (root == NULL) return false;           // special case 1: tree is empty       return remove2(root, root, item);         // normal case} bool BST::remove2(BTNode *pre, BTNode *cur, type item) {        // Turn back when the search reaches the end of an external path       if (cur == NULL) return false;        // normal case: manage to find the item to be removed       if (cur->item.compare2(item)){              if (cur->left == NULL || cur->right == NULL)                      case2(pre, cur);     // case 2 and case 1: cur has less than 2 sons              else                      case3(cur);          // case 3, cur has 2 sons              count–;                            // update the counter              return true;       }        // Current node does NOT store the current item -> ask left sub-tree to check       //if (cur->item > item)       if (cur->item.compare1(item))              return remove2(cur, cur->left, item);        // Item is not in the left subtree, try the right sub-tree instead       return remove2(cur, cur->right, item);}  void BST::case2(BTNode *pre, BTNode *cur) {        // special case: delete root node       if (pre == cur) {              if (cur->left != NULL)      // has left son?                      root = cur->left;              else                      root = cur->right;               free(cur);              return;       }        if (pre->right == cur) {           // father is right son of grandfather?               if (cur->left == NULL)                    // father has no left son?                      pre->right = cur->right;                  // connect gfather/gson              else                      pre->right = cur->left;       }       else {                                     // father is left son of grandfather?              if (cur->left == NULL)                    // father has no left son?                       pre->left = cur->right;                          // connect gfather/gson              else                      pre->left = cur->left;       }        free(cur);                                 // remove item}  void BST::case3(BTNode *cur) {       BTNode        *is, *isFather;        // get the IS and IS_parent of current node       is = isFather = cur->right;       while (is->left != NULL) {              isFather = is;              is = is->left;       }        // copy IS node into current node       cur->item = is->item;        // Point IS_Father (grandfather) to IS_Child (grandson)       if (is == isFather)              cur->right = is->right;            // case 1: There is no IS_Father          else              isFather->left = is->right; // case 2: There is IS_Father        // remove IS Node       free(is);} BST.h#ifndef BT_type#define BT_type #include      “BTNode.h”#include      “Queue.h”  struct BST {               int           count;              BTNode *root;               // print operation for BST (same as BT)                                              void preOrderPrint2(BTNode *);     // recursive function for preOrderPrint()              void inOrderPrint2(BTNode *);      // recursive function for inOrderPrint()              void postOrderPrint2(BTNode *);    // recursive function for postOrderPrint()               // sample operation (extra functions) – same as BT              void countNode2(BTNode *, int &);         // recursive function for countNode()              bool fGS2(type, BTNode *);                              // recursive function for findGrandsons(): to find the grandfather              void fGS3(BTNode *, int);                        // recursive function for findGrandsons(): to find the grandsons after the grandfather has been found                            // basic functions for BST              void insert2(BTNode *, BTNode *);         // recursive function for insert() of BST              void case3(BTNode *);                                   // recursive function for remove()              void case2(BTNode *, BTNode *);           // recursive function for remove()              bool remove2(BTNode *, BTNode *, type);  // recursive function for remove()                 // basic functions for BST              BST();              bool empty();              int size();              bool insert (type);         // insert an item into a BST              bool remove(type);                 // remove an item from a BST                            // print operation for BST (same as BT)              void preOrderPrint();                     // print BST node in pre-order manner              void inOrderPrint();               // print BST node in in-order manner              void postOrderPrint();                    // print BST node in post-order manner              void topDownLevelTraversal();      // print BST level-by-level               // sample operation (extra functions) – same as BT              int countNode();            // count number of tree nodes              bool findGrandsons(type);   // find the grandsons of an input father item                      };    #endif BTNode.cpp#include #include “BTNode.h” using namespace std; BTNode::BTNode(type newItem) {       item = newItem;       left = right = NULL;} BTNode.h#ifndef BTNode_type#define BTNode_type #include “Student.h” using type = Student; struct BTNode {               type   item;              BTNode *left, *right;              BTNode(type);};  #endif Node.cpp#include #include “Node.h”   Node::Node(type2 newItem) {       item = newItem;       next = NULL;}Node.h#ifndef Node_type#define Node_type #include “BTNode.h” using type2 = BTNode *; struct Node {                     type2         item;              Node   *next;              Node(type2);};  #endif Queue.cpp#include #include “Queue.h” using namespace std;   Queue::Queue() {       head = tail = NULL;       count = 0;}  bool Queue::empty() {       if (count == 0) return true;       return false;}  int Queue::size() {       return count;}  bool Queue::enqueue(type2 newItem) {// Any simplification can be done on code below?       Node   *tmp = new Node(newItem);        if (!tmp) return false;       if (empty()) {              head = tail = tmp;              count++;              return true;       }       count++;       tail->next = tmp;       tail = tmp;       return true;}  bool Queue::dequeue(type2 &itemExtracted) {       Node   *cur = head;        if (empty()) return false;       count–;       itemExtracted = head->item;       head = head->next;       free(cur);       if (count == 0) tail = NULL;       return true;}  Node *Queue::find(type2 record) {       Node   *cur;        cur = head;       for (; cur != NULL;) {              if (cur->item == record) return cur;              cur = cur->next;       }       return NULL;} Queue.h#ifndef Queue_type#define Queue_type #include      “Node.h” struct Queue {              int           count;              Node   *head;              Node   *tail;              Queue();              bool empty();              int size();              bool enqueue(type2);               bool dequeue(type2 &);              Node   *find(type2);};  #endif Student.cpp#include  #include “Student.h”  using namespace std;  Student::Student(){       strcpy(name, ” “);       id = 0;       strcpy(address, ” “);       strcpy(DOB, ” “);       strcpy(course, ” “);       strcpy(phone_no, ” “);       cgpa = 0.0; }  void Student::print(ostream &out){       out << "nName: " << name;       out << "nID: " << id;       out << "nAddress: " << address;       out << "nDate of Birth: " << DOB;       out << "nPhone No: " << phone_no;       out << "nCourse: " << course;       out << "nCGPA: " << cgpa;       out << "n"; }  bool Student::compare1(Student p2){       if (id > p2.id)              return true;       return false; }  bool Student::compare2(Student p2){       if (id == p2.id)              return true;       return false;}   bool Student::compare3(int id2){       if (id == id2)              return true;       return false;} Student.h#ifndef Student_type#define Student_type  using namespace std; //student infostruct Student{        char name[30];           int id;       char address[100];       char DOB[20];       char course[5];       char phone_no[10];       double cgpa;              Student();       void print(ostream &);       bool compare1(Student); //using > to compare 2 students struct variable       bool compare2(Student); //using == to compare 2 students struct variable       bool compare3(int); //using == to compare student id with the id passed in       }; #endifEngineering & TechnologyComputer ScienceFICT UCCD1024Share Question