Consider the following declarations when answering parts h: class b_node {public
ID: 3577637 • Letter: C
Question
Consider the following declarations when answering parts h: class b_node {public: string client; b_node *right, *left;}; class BST {public: BST(); int Count_Nodes_with_Two_Children(b_node *r); private: b_node *root;}; Implement the recursive function called "Count_Nodes_with _Two_Children" that returns an integer representing the number of nodes with two children in a binary search tree given a pointer to the root of the tree. Assume that the function is originally invoked by another member function.Explanation / Answer
#include <iostream>
using namespace std;
class b_node
{
public:
string client;
b_node *right, *left;
};
class BST
{
public:
BST();
int Count_Nodes_with_Two_Children(b_node *r);
};
int BST::Count_Nodes_with_Two_Children(b_node *r)
{
if(r == NULL || r->left == NULL || r->right == NULL) //If there is no node, or the node has either 0, or 1 children.
return 0; //Don't increase the count.
return 1 + Count_Nodes_with_Two_Children(r->left) + Count_Nodes_with_Two_Children(r->right); //If not increase the count, and count the children.
}