Create a starter and a recursive function counts the number of nodes at each level. Uses a vector parameter sent by reference. (Function declarations are already done in bst.h)

See more:

C++

//Create a starter and a recursive function for each of following: (function declarations are already done in BST.h)

//count the leaves

//determine the height
// Create a starter and a recursive function counts the number of nodes at each level. Uses a vector parameter sent by reference. (function declarations are already done in BST.h)

BST.H

#ifndef BST_H
#define BST_H

#include
#include
using namespace std;

template
class TreeNode
{
public:
   T element; // Element contained in the node
   TreeNode* left; // Pointer to the left child
   TreeNode* right; // Pointer to the right child

   TreeNode(const T& e) // Constructor
   {
       this->element = e;
       left = nullptr;
       right = nullptr;
   }
};


template
class BST
{
public:
   BST(); // No-arg constructor
   BST(vector elements[]);
  
   ~BST(); // Destructor
   int getSize() const;
   bool search(const T& e) const;
   bool insert(const T& e);
   bool remove(const T& e);
   void inorder() const;
   void clear();
   void printTree() const;


   //Question = 1 : uncomment the following and these definitions, the recursive overloaded functions, and test:
   /*
   int getNumberOfLeaves() const;
   int height() const;
   */

   //Question -2: uncomment the following and these definitions, the recursive overloaded functions, and test:


   //Note: the vector is declared and initialized (clear() ) here, the recurisive call is made, and then the vector is printed out
   //void nodesPerLevel() const;


protected:
   TreeNode* root;
   int size;
  
private:
   void inorder(const TreeNode* root) const;
   void clear(const TreeNode* root);

   void printTree(const TreeNode* root, int indent) const;

   //Question =1: uncomment the following, and add the definitions (code them)
   /*
   int getNumberOfLeaves(const TreeNode* root) const;
   int height(const TreeNode* root, int level) const;
   */

   //Question =2 :uncomment the following, and add the definition (code it)


   //void nodesPerLevel(vector& nodes, const TreeNode* root, int l) const;
};

template
BST::BST()
{
   root = nullptr;
   size = 0;
}

template
BST::BST(vector elements[])
{
   root = nullptr;
   size = 0;
   for (int i = 0; i < elements->size(); i++)
       insert(elements[i]);
}


/* Destructor */
template
BST::~BST()
{
   clear();
}

/* Get the number of nodes in the tree */
template
int BST::getSize() const
{
   return size;
}

/* Return true if the element is in the tree */
template
bool BST::search(const T& e) const
{
   TreeNode* current = root; // Start from the root

   while (current != nullptr)
       if (e < current->element)
       {
           current = current->left; // Go left
       }
       else if (e > current->element)
       {
           current = current->right; // Go right
       }
       else // Element e matches current.element
           return true; // Element e is found

   return false; // Element e is not in the tree
}

// Insert element e into the binary tree
// Return true if the element is inserted successfully
// Return false if the element is already in the list
template
bool BST::insert(const T& e)
{
   if (root == nullptr)
       root = new TreeNode(e); // Create a new root
   else
   {
       // Locate the parent node
       TreeNode* parent = nullptr;
       TreeNode* current = root;
       while (current != nullptr)
           if (e < current->element)
           {
               parent = current;
               current = current->left;
           }
           else if (e > current->element)
           {
               parent = current;
               current = current->right;
           }
           else
               return false; // Duplicate node not inserted

                           // Create the new node and attach it to the parent node
       if (e < parent->element)
           parent->left = new TreeNode(e);
       else
           parent->right = new TreeNode(e);
   }

   size++;
   return true; // Element inserted
}


/* Delete an element e from the binary tree.
* Return true if the element is deleted successfully
* Return false if the element is not in the tree */
template
bool BST::remove(const T& e)
{
   // Locate the node to be deleted and also locate its parent node
   TreeNode* parent = nullptr;
   TreeNode* current = root;
   while (current != nullptr)
   {
       if (e < current->element)
       {
           parent = current;
           current = current->left;
       }
       else if (e > current->element)
       {
           parent = current;
           current = current->right;
       }
       else
           break; // Element e is in the tree pointed by current
   }

   if (current == nullptr)
       return false; // Element e is not in the tree

                   // Case 1: current has no left children
   if (current->left == nullptr)
   {
       // Connect the parent with the right child of the current node
       if (parent == nullptr)
       {
           root = current->right;
       }
       else
       {
           if (e < parent->element)
               parent->left = current->right;
           else
               parent->right = current->right;
       }

       delete current; // Delete current
   }
   else
   {
       // Case 2: The current node has a left child
       // Locate the rightmost node in the left subtree of
       // the current node and also its parent
       TreeNode* parentOfRightMost = current;
       TreeNode* rightMost = current->left;

       while (rightMost->right != nullptr)
       {
           parentOfRightMost = rightMost;
           rightMost = rightMost->right; // Keep going to the right
       }

       // Replace the element in current by the element in rightMost
       current->element = rightMost->element;

       // Eliminate rightmost node
       if (parentOfRightMost->right == rightMost)
           parentOfRightMost->right = rightMost->left;
       else
           // Special case: parentOfRightMost->right == current
           parentOfRightMost->left = rightMost->left;

       delete rightMost; // Delete rightMost
   }

   size--;
   return true; // Element inserted
}

/* Inorder traversal Note: we use a public "starter" method, and a private recursive method called from the starter*/
//starter
template
void BST::inorder() const
{
   inorder(root);
   cout << endl;
}

/* recursive Inorder traversal from a subtree */

template
void BST::inorder(const TreeNode* root) const
{
   if (root == nullptr)
       return;
   inorder(root->left);
   cout << root->element << " ";
   inorder(root->right);
}

/* Remove all nodes from the tree. Two methods, same design as inorder */
template
void BST::clear()
{
   clear(root);
   size = 0;
   root = nullptr;
}

template
void BST::clear(const TreeNode* root)
{
   if (root == nullptr)
       return;
   clear(root->left);
   clear(root->right);
   delete root;
   return;
}


template
void BST::printTree() const {
   printTree(root, 0);
}


template
void BST::printTree(const TreeNode* root, int indent) const {
   if (root == nullptr)
       return;

   // Uses a reverse inorder traversal. print the right side first
   printTree(root->right, indent + 1);
   //print the current node
   for (int i = 0; i < indent; i++)
       cout << " ";
   cout << root->element << endl;
   // print the left side last
   printTree(root->left, indent + 1);
}


#endif

What I have tried:

I am trying to write the starter and recursive function to get the number of leaves, height of tree and number of nodes in each level. However, I did not figure it out, that how to do this. Could anyone here please help me in complete my code. I did overall code, you just have to help me in getting these three.