Consider the following declarations when answering parts h: class b_node {public
ID: 3825119 • 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;}; h. 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 <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Function to get the count of leaf nodes in a binary tree*/
unsigned int getLeafCount(struct node* node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right==NULL)
return 1;
else
return getLeafCount(node->left)+
getLeafCount(node->right);
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
/*create a tree*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
/*get leaf count of the above created tree*/
printf("Leaf count of the tree is %d", getLeafCount(root));
getchar();
return 0;
}