Learn basic concept of c , c++ and python programming in regularcodes.com

Count leaf node of binary search tree (iterative approach) using queue

Time complexity of this program O(n)

Accepted Output

Given BST data is:

555, 483, 593, 437, 518, 594, 475, 514, 467, 514

View Tree

In this tree leaf node are [ 467, 514, 594 ].

Result :

Number of leaf Node is [3]

Given BST data is:

515, 93, 30, 20, 40, 104, 115, 134, 610

View Tree

Result :

Number of leaf Node is [4]

Below in C implementation of this problem. Iterative approach.

Click To Visualize Code

/*Help of this program we are learning how to count BST leaf node. 
Using Queue data structure*/

/* Include header file*/
#include<stdio.h>
#include<stdlib.h>

/* Define struct of BST */
struct Tree{
   int data;/*Data field*/
   struct Tree*left_child,*right_child;/*Pointer field*/
};

/*structure of Queue*/
struct Queue{
   struct Tree*node;
   struct Queue*next;
};

/*function declaration section*/
void insert_node(struct Tree**,int);
struct Tree* free_node(struct Tree*);
void dequeue(struct Queue**);
void enqueue(struct Queue**,struct Tree*);

/*  Create and insert newly BST Node.*/
void insert_node(struct Tree**root,int value){
   
   /* Create dynamic memory block and assign that address on new_node pointer */
   struct Tree*new_node=(struct Tree*)malloc(sizeof(struct Tree));
   
    /* Check newly memory block are created or not*/
   if(new_node)
   {
      /* Memory block are created successful */

      /* Assign left_child and right_child pointer value to NULL */
      
      new_node->left_child=NULL;
       
       new_node->right_child=NULL;

       /* Assign data value */
      new_node->data=value;
        
        /*Check BST root Pointer NULL or Not NULL*/ 
      if(*root)
      {
         
         struct Tree*temp=*root;

            /* find position to insert new_node.  */ 
         while(temp)
         {
            if(temp->data>value)
            {
               if(temp->left_child!=NULL)
               {
                  /*temp pointer Move to left_child memory block */
                  temp=temp->left_child;
               }
               else
               {
                  /*Assign newly created memory block address to temp->left_child pointer*/
                  
                  temp->left_child=new_node;
                  /*Break loop*/
                  break;
               }
            }
            else
            {  
               
               if(temp->right_child!=NULL)
               {
                  /*temp pointer Move to right_child memory block */
               
                  temp=temp->right_child;
               }
               else
               {
                  /*Assign newly created memory block address to temp->right_child pointer*/
                  temp->right_child=new_node;
                  break;
               }
            }
         }
         
      }
      else{

         /*When root pointer is NULL that means no element of BST tree then Assign this newly created memory block to root pointer*/
         *root=new_node;
      }
      
   }
   else {

      /*Not created memory by malloc function*/
       printf("\n memory Overflow");   

   }

}


/* Help of this function Free BST Nodes */
struct Tree* free_node(struct Tree*temp){
   if(temp){
      temp->left_child=free_node((temp->left_child));
      temp->right_child=free_node(temp->right_child);
      free(temp);
      temp=NULL;
   }
   return NULL;
}
/*insert queue data and count leaf bst nodes*/
void enqueue(struct Queue**queue,struct Tree*temp){

   if(!temp){
      printf("\n No element of this BST");
      return;
   }
   /* Create first Queue node and assign on address of new_node. */ 
   struct Queue*help=NULL,*start=NULL,*new_node=(struct Queue*)malloc(sizeof(struct Queue));
   
   /* Assign (next pointer) value is NULL. */
   new_node->next=NULL;
   
   /* Assign Tree root node address are of this newly created memory block node pointer.*/
   new_node->node=temp;
   
    /* Assign on first node address of queue pointer. */
   *queue=new_node;
   

   help=start=new_node;
    
    int result=0,status=0;
   
   /* Check Queue pointer is Not NULL  */
   while(help)
   {
       /* Assign status variable value 1 (assume that current node is leaf node)*/
      status=1;

      if(help->node->left_child){
         /*Create memory block of structure queue and assign on address new_node pointer*/
           new_node=(struct Queue*)malloc(sizeof(struct Queue));
          
         /* Assign (next pointer) value is NULL. */
          new_node->next=NULL;

         
          new_node->node=help->node->left_child;
          
            /* Queue last node pointed to this new_node*/
          start->next=new_node;

          /*start pointed to new_node*/
          start=new_node;

          /* Change status value that means it is not leaf node*/
          status=0;

      }
      if(help->node->right_child){
         /* Create memory block of structure queue and assign on address new_node pointer*/
          new_node=(struct Queue*)malloc(sizeof(struct Queue));

          /* Assign (next pointer) value is NULL. */
          new_node->next=NULL;

          new_node->node=help->node->right_child;

          /* Queue last node pointed to this new_node*/
          start->next=new_node;

          /*start pointed to new_node*/
          start=new_node;

          /* Change status value that means it is not leaf node*/
          status=0;
      }
      if(status==1){
         
         /*increment leaf node*/
         result++;
      }

        /*Move next memory block*/
        help=help->next;
   }
     /* Print result*/ 
   printf("\n Number of leaf Node is [%d]",result);
}

/* Free queue node */
void dequeue(struct Queue**queue){
   
   struct Queue*temp=*queue;
   while(temp)
   {
      *queue=temp->next;
      temp->next=NULL;
      free(temp);
      temp=NULL;
      temp=*queue;
   }
   printf("\n Free Memory of Queue\n");
}

/* Show BST node data using this function */
void inorder_show(struct Tree*temp){

   if(temp){
      inorder_show(temp->left_child);
      printf("  %d",temp->data);
      inorder_show(temp->right_child);
   }else
   return;

}


/*Main function*/
int main()
{/*start execution*/

    /* BST structure pointer*/
    struct Tree*root=NULL;

    /*Suppose following data are inserted BST */
    insert_node(&root,140);
    insert_node(&root,90);
    insert_node(&root,30);
    insert_node(&root,220);
    insert_node(&root,40);
    insert_node(&root,104);
    insert_node(&root,115);
    insert_node(&root,104);
    insert_node(&root,240);

   
    printf("\n BST Data is :"); 
    inorder_show(root);
   
    struct Queue*queue=NULL;
   
    
      enqueue(&queue,root);

    dequeue(&queue);

    printf("\n Free BST node\n"); 
    /*Free BST Node*/
    root=free_node(root);

   
    return 0;
    /* End execution of program */
}

Output

 BST Data is :  30  40  90  104  104  115  140  220  240
 Number of leaf Node is [3]
 Free Memory of Queue

 Free BST node

Visualization

Circular Single Linked list

Circular Doubly Linked list

Sorting

Count leaf node of binary search tree (iterative approach) using queue

Accepted Output

Visualization

Comments