Constructing and maintaining a complete binary tree

Problem statement:


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

• Insert a given key and perform inorder

• Replace ALL occurrences of the given key with the then Last Element of the Tree. Then Remove the last node.

• Query -> return number of occurrences of the key

• 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
#include
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/////////

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.

StackExchange Code Review Q#83268, answer score: 3