Write efficient functions that take only a pointer to the root of a binary searc

Question

Write efficient functions that take only a pointer to the root of a binary search tree, T, and compute:

a. The number of nodes in T.
b. The number of leaves in T.
c. The number of full nodes (a full node is a node with two children) in T.

Your main program reads a set of values from DataIn file into the tree, then call the above functions to compute. The main program should print out the answer of each function (a#, b#, c#) as follows, see sample data input / output.

Sample data input: (for a. b. c.): 314596807

Sample data output: a#, b#, c#

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);

}

/*Driver program to test above functions*/

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;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.