COUNTING THE NUMBER OF NODES IN A BINARY SEARCH TREE

Program

A complete C program to count the number of nodes is as follows:

#include <stdio.h>
#include <stdlib.h>
struct tnode
{
   int data;
   struct tnode *lchild, *rchild;
};
int count(struct tnode *p)
    {
               if( p == NULL)
      return(0);
              else
      if( p->lchild == NULL && p->rchild == NULL)
                return(1);
      else
                return(1 + (count(p->lchild) + count(p->rchild)));

    }

struct tnode *insert(struct tnode *p,int val)
   {
      struct tnode *temp1,*temp2;
      if(p == NULL)
      {
         p = (struct tnode *) malloc(sizeof(struct tnode)); /* insert the new node as root node*/
            if(p == NULL)
              {
          printf("Cannot allocate\n");
          exit(0);
               }
           p->data = val;
           p->lchild=p->rchild=NULL;
      }
     else
     {
      temp1 = p;
      /* traverse the tree to get a pointer to that node whose child will be the newly created node*/
     while(temp1 != NULL)
     {
       temp2 = temp1;
       if( temp1 ->data > val)
            temp1 = temp1->lchild;
       else
            temp1 = temp1->rchild;
     }
     if( temp2->data > val)
     {
        temp2->lchild = (struct tnode*)malloc(sizeof(struct tnode)); /
*inserts the newly created node
      as left child*/
         temp2 = temp2->lchild;
         if(temp2 == NULL)
              {
         printf("Cannot allocate\n");
         exit(0);
             }
        temp2->data = val;
        temp2->lchild=temp2->rchild = NULL;
   }
   else
   {
      temp2->rchild = (struct tnode*)malloc(sizeof(struct tnode));/ *inserts the newly created node
  as left child*/
     temp2 = temp2->rchild;
     if(temp2 == NULL)
          {
     printf("Cannot allocate\n");
     exit(0);
         }
     temp2->data = val;
     temp2->lchild=temp2->rchild = NULL;
  }
  }
  return(p);
  }
  /* a function to binary tree in inorder */
  void inorder(struct tnode *p)
      {
         if(p != NULL)
           {
             inorder(p->lchild);
            printf("%d\t",p->data);
           inorder(p->rchild);
           }
      }
void main()
{
   struct tnode *root = NULL;
   int n,x;
   printf("Enter the number of nodes\n");
   scanf("%d",&n);
   while( n --- > 0)
      {
         printf("Enter the data value\n");
         scanf("%d",&x);
         root = insert(root,x);
     }
      inorder(root);
     printf("\nThe number of nodes in tree are :%d\n",count(root));
}

Explanation

• Input: 1. The number of nodes that the tree to be created should have
  2. The data values of each node in the tree to be created
• Output: 1. The data value of the nodes of the tree in inorder
  2. The count of number of node in a tree.