Constructing and maintaining a complete binary tree

Question

Problem statement:

Create and maintain a Complete Binary Tree in C. Include the following operations.

1. Insert a given key and perform inorder
2. Replace ALL occurrences of the given key with the then Last Element of the Tree. Then Remove the last node.
3. Query -> return number of occurrences of the key
4. Size -> Given a key, return the number of nodes in the subtree

I have written this code, which passes all the public test cases. Is there a better way to maintain this structure, for example, with the help of an array? I am implementing every DS from scratch.

#include<stdio.h>
#include<stdlib.h>
int lastLabel = 0;

struct node
{
    int data;
    int label;
    struct node* parent;
    struct node* rightChild;
    struct node* leftChild;
};

struct node* createNode(int d)
{
   struct node* newN = (struct node*)malloc(sizeof(struct node));
   newN->data = d;
   newN->leftChild  = '\0';
   newN->rightChild = '\0';
   lastLabel++;
   newN->label      = lastLabel;
   return newN;
}
struct Queue
{
   int front,rear;
   int size;
   struct node** array;
};

typedef struct tree
{
   struct node* root;
   int size;
}BinaryTree;

////////Binary Tree Helper Functions//////////////////////
BinaryTree* createTree()
{
     BinaryTree* t = (BinaryTree*)malloc(sizeof(BinaryTree));
     t->root       = '\0';
     t->size       = 0;
     return t;
}

int size(BinaryTree *t)
{
   return t->size;
}

struct node* root(BinaryTree *t)
{
    return t->root;
}

struct node* parent(struct node* n)
{
   return n->parent;
}

int isInternal(struct node *n)
{
   return n->leftChild != '\0' || n->rightChild != '\0';
}

int isExternal(struct node *n)
{
        return !isInternal(n);
}

int isRoot(struct node* n)
{
   return n->parent == '\0';
}

int hasBothChild(struct node* temp)        
{
      if((temp!= '\0') && (temp->leftChild != '\0') && (temp->rightChild != '\0')) return 1;
}
////////Binary Tree Helper Functions//////////////////////

/////////Queue Helper Functions//////////////////////////
//
//
//createQueue takes queueSize as input and returns a '\0'-initialized queue
struct Queue* createQueue(int size)
{
   struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
   queue->front = queue->rear = -1;
   queue->size  = size;

   queue->array = (struct node**)malloc(queue->size * sizeof(struct node*));
   int i;
   for(i = 0; i < size; i++) queue->array[i] = '\0';
   return queue;
}
//check if Queue is empty
int isEmpty(struct Queue* queue)               
{
   return queue->front == -1;
}
//check if Queue is Full
int isFull(struct  Queue* queue)                 
{
   return (queue->rear == queue->size-1);
}
//check if Queue has only one Item
int hasOnlyOneItem(struct Queue* queue)         
{
  return (queue->front == queue->rear);
}
//ENQUEUE
void Enqueue(struct node* root, struct Queue *queue)
{
   if(isFull(queue)) return;
   queue->array[++queue->rear] = root;
   if(isEmpty(queue))  ++queue->front;
}
//DEQUEUE
struct node* Dequeue(struct Queue* queue)
{
       if(isEmpty(queue))  return '\0';
       struct node* temp = queue->array[queue->front];
       if (hasOnlyOneItem(queue))     queue->front = queue->rear = -1;
       else                           ++queue->front;
       return temp;
}
//Get Front of the Queue
struct node* getFront(struct Queue* queue) 
{
      return queue->array[queue->front];
}
/////////Queue Helper Functions//////////////////////////
//Helper function to find the number of nodes of a particular subTree
int sizeFind(struct node* stree)
{
  if(stree == '\0') return 0;
  else              return(sizeFind(stree->leftChild) + 1 + sizeFind(stree->rightChild));
} 

//Helper function to find the a particular nodes given the node's key
int sizeQuery(struct node* root,int key, int size)
{
   struct Queue *queue     = createQueue(size);
   struct node  *temp_node   = root;

   while(temp_node)
   {
      if(temp_node->data == key)
      {
            return sizeFind(temp_node);
      }
      if(temp_node->leftChild != '\0')
      {
             Enqueue(temp_node->leftChild, queue);
      }
      if(temp_node->rightChild != '\0')
      {
        Enqueue(temp_node->rightChild, queue);
      }
      temp_node = Dequeue(queue);
   }
   return 0; 
}


//insert data in the pre-existing Complete Binary Tree
void insert(struct node** root, int data, struct Queue* queue)
{
   struct node* temp = createNode(data);
   if(!*root)      
   {
       *root = temp;
   }
   else     
   {
       struct node* front = getFront(queue);
       if((front->leftChild) == '\0')
       {
          front->leftChild  = temp; 
          temp->parent = front;
       }
       else if((front->rightChild) == '\0')        
       { 
         front->rightChild = temp;
         temp->parent      = front;
       }
       if(hasBothChild(front))       Dequeue(queue);
   }   
   Enqueue(temp,queue);
}
//perform Level Order Traversal
void levelOrder(struct node* root, int size)
{
   struct Queue* queue = createQueue(size);
   Enqueue(root, queue);
   int label = 0;
   while(!isEmpty(queue))
   {
      struct node* temp = Dequeue(queue);
      label++;
      temp->label = label;
      if(temp->leftChild)  Enqueue(temp->leftChild,  queue);
        if(temp->rightChild) Enqueue(temp->rightChild, queue);
   }
}
//perform InOrder Traversal                              
void inOrder(struct node* root)
{
   if(root == '\0') return;
   if(isInternal(root)) inOrder(root->leftChild);
   printf("%d ", root->data);
   if(isInternal(root)) inOrder(root->rightChild);
}
//perform Query 
int Query(struct node* root,int key,int size)
{
   int count = 0;
   int rear,front;
   struct Queue *queue     = createQueue(size);
   struct node  *temp_node   = root;                                                                   
   while(temp_node)
   {
      if(temp_node->data == key)
      {
            count++;
      }
      if(temp_node->leftChild != '\0')
      {
             Enqueue(temp_node->leftChild, queue);
      }
      if(temp_node->rightChild != '\0')
      {
             Enqueue(temp_node->rightChild, queue);
      }
      temp_node = Dequeue(queue);
   }
   return count;
}
//Get Pointer will return the node given the Root of the CBT and the Label
struct node* getPointer(int label,struct node* root)
{
    struct node* parentPointer;
    struct node* child;
    if(root!= '\0' && label == 1) return root;
    else
    {
         parentPointer    =  getPointer(label/2, root);
         child            =   parentPointer->leftChild;
//         printf("What should have  Happened here  Label %d %d %d \n",label, child->data,child->label);
//         printf("What should have  Happened here  Label %d %d %d \n",label, parentPointer->leftChild->data, parentPointer->leftChild-> label);
         if(parentPointer != '\0' && child != '\0')
         {  
          if((parentPointer->leftChild->label) == label)   return parentPointer->leftChild;
          else                                             return parentPointer->rightChild;
         }
    }
}
//The helper function will remove the node containing the Key(multiple instances possible), then it would replace that node with the Last Node
struct node* Delete(struct node* root,int key,int size)
{
    int count = 0;
    int rear,front;
    struct Queue *queue       = createQueue(size);
    struct node  *temp_node   = root;
    while(temp_node)
    {
      if(temp_node->data == key)
      {
        struct node* lastValue = getPointer(lastLabel,root);
        if(lastValue != '\0') 
        {
          temp_node->data  = lastValue->data;
          if(lastValue->label == lastValue->parent->leftChild->label) 
                                 lastValue->parent->leftChild = '\0';
          else                        
                                 lastValue->parent->rightChild = '\0';
        }  
        free(lastValue);
        lastLabel--;
      }
      if(temp_node != NULL)
      {  
         if(temp_node->leftChild != '\0')
        {
           Enqueue(temp_node->leftChild, queue);
        }
        if(temp_node->rightChild != '\0')
        {
          Enqueue(temp_node->rightChild, queue);
        }
      }  

      if(!(temp_node != NULL && temp_node->data == key)) temp_node = Dequeue(queue);
   }
   return root;
}

int main()
{
   int num_items;
   int key;
   int num_Ops;
   char op;
   int op_key;
   int ctr;
   int qcount;
   int i;
   int stree_ctr;
   scanf("%d",&num_items); 
   struct node*  root  = '\0';
   struct Queue* queue = createQueue(num_items);
   for(ctr = 0; ctr < num_items; ctr++)
   {
      scanf("%d",&key);
      insert(&root,key, queue);
   }
   levelOrder(root,num_items);
   inOrder(root);
   printf("\n");
   //num_items is just the initial number of elements
   scanf("%d",&num_Ops);
   for(i = 0; i < num_Ops ; i++)
   {

     while((op = getchar())== '\n');
     scanf("%d",&op_key);
     if(op ==  'i') 
      {
                       insert(&root,op_key,queue);
                       inOrder(root);
                       printf("\n");
      }
      else if(op == 'q')
      { 
                       qcount = Query(root,op_key,lastLabel);
                       printf("%d\n",qcount);
      }               
      else if(op == 's')
      {
                       stree_ctr = sizeQuery(root,op_key,lastLabel);
                       printf("%d\n",stree_ctr);
      }
      else if(op == 'r')
      {
                       root = Delete(root,op_key,lastLabel);
                       inOrder(root);
                       printf("\n");
      }
   }
   return 0;
}

Answer 1

I see a number things that may help you improve your code.

Rethink your data structures

The code comments claim that the structure being implemented is a tree, but there seems to be a Queue object tangled up in your tree. This both complicates the tree code and confuses the reader of the code. It would be better to strive for a clean tree implementation instead. For example, the current Query routine both leaks memory and is overly complex because it also incorporates a Queue. Here's a simpler recursive rewrite:

int Query(struct node* root, int key)
{
    if (root == NULL)
        return 0;
    int count = Query(root->leftChild, key);
    if (root->data == key)
        count++;
    count += Query(root->rightChild, key);
    return count;
}

Use NULL instead of '\0' for pointers

The value '\0' is a single character, but the value NULL is an implementation-defined null-pointer constant. It is not guaranteed to have the value 0.

Only check conditions once

The current code for the inOrder routine is this (with the previous note implemented):

void inOrder(struct node* root)
{
   if(root == NULL) return;
   isInternal(root)) inOrder(root->leftChild);
   printf("%d ", root->data);
   if(isInternal(root)) inOrder(root->rightChild);
}

However, there's no need for the call to isInteral. If the check is eliminated, it only means that the first check will catch the issue on the next recursive call. In other words, the code could be cleaned up like this:

void inOrder(struct node* root)
{
   if(root == NULL) 
       return;
   inOrder(root->leftChild);
   printf("%d ", root->data);
   inOrder(root->rightChild);
}

Eliminate unused variables

Unused variables are a sign of poor code quality, so eliminating them should be a priority. In this code, Query and Delete both define but do not use rear and front. Your compiler is probably also smart enough to tell you that, if you ask it to do so.

Eliminate global variables where practical

The code declares and uses a global variable, lastLabel. Global variables obfuscate the actual dependencies within code and make maintainance and understanding of the code that much more difficult. It also makes the code harder to reuse. For all of these reasons, it's generally far preferable to eliminate global variables and to instead pass pointers to them. That way the linkage is explicit and may be altered more easily if needed.

Ensure every control path returns a proper value

The hasBothChild routine returns 1 under some set of conditions but then doesn't return anything at all otherwise. This is an error. The code could instead be written like this:

int hasBothChild(struct node* temp)        
{
    return temp != NULL && 
        temp->leftChild != NULL && 
        temp->rightChild != NULL;
}

There is a similar problem with getPointer.

Create subfunctions that can be used multiple places

This code has multiple places that it looks for a node with a particular value. That is a strong clue that it should be its own routine. For example:

// returns a pointer to the first node with matching key
// or NULL if none found
struct node *find(struct node *root, int key)
{
    if (root == NULL)
        return NULL;
    if (root->data == key)
        return root;
    root = find(root->leftChild, key);
    if (root == NULL)
        root = find(root->rightChild, key);
    return root;
}

Now your sizeQuery routine becomes extremely simple:

//Count the nodes in the subtree with the given key
int sizeQuery(struct node* root,int key)
{
    return sizeFind(find(root, key));
}

Eliminate memory leaks

The code does not release all memory that it allocates. That's a bug that should be fixed. Eliminating the Queue structure entirely should help with that considerably.

Omit return 0 at the end of main

The compiler will automatically generate a return 0; at the end of main so it is not necessary to supply your own.

Answer 2

I'll give this a quick review, as I haven't spent much time with tree implementations in C.

• It's more common to have a space in #include lines:

  #include <stdio.h>
  #include <stdlib.h>
  

• You may not need lastLabel to be a global if you can just pass it to the necessary functions. There aren't very many of them, either.

• If you have C99, you can use the bool type for your "is" functions. You would need to include <stdbool.h> in order to use them.

• This isn't very readable formatting:

  if (hasOnlyOneItem(queue))     queue->front = queue->rear = -1;
  else                           ++queue->front;
  

  You should at least put it in this form:

  if (hasOnlyOneItem(queue))
      queue->front = queue->rear = -1;
  else
      ++queue->front;
  

  but for the sake of maintainability and fewer opportunities for bugs, use this one:

  if (hasOnlyOneItem(queue))
  {
      queue->front = queue->rear = -1;
  }
  else
  {
      ++queue->front;
  }
  

• The comments and the function name don't quite align:

  //Helper function to find the number of nodes of a particular subTree
  int sizeFind(struct node* stree)
  

• Some of your functions are in PascalCase and others are in camelCase. You should just choose one and stay consistent with it.

  The name sizeFind sounds similar enough to size, which still isn't accurate enough based on the comment. You may consider something like subtreeSize.

• While it is common in C to declare variables at the top, it is still discouraged as it can be bad for maintenance purposes.

  For instance, in main(), it may be quite easy to lose track of a variable's usage. If you end up no longer needing one, the compiler won't tell you unless you have warnings turned all the way up (ideally with -Wall).

• Also in main(), I don't think you need to ask the user a preset number of operations. Doing so will restrict them to that number, and they will have to start the program again if more operations are desired, or have to do something else if fewer operations are desired. You can instead specify a sentinel value and have the loop stop whenever that value is entered.

  In addition, it may be more readable to use a switch statement here instead. It'll also allow you to perform a default action if an unknown value is entered, such as terminating the loop.