Complete Binary Trees

Created November 26, 2021

In this post, I'm gonna share some basic knowledge about a concept of data structures called "Complete Binary Trees". We're just gonna build upon the concept of Binary trees here. So if you don't know what binary trees are you can check out my post here on Binary Trees.

What are Complete Binary Trees?

They're just simple binary trees that are filled from left to right direction. All its levels should be full from the left to the right direction.

These illustrations might help you get a little bit idea about how they should and should not look like - completeBT.gif notcompleteBT.gif

The Structure

By "structure" I mean the structure of the node(smallest unit of a binary tree). As a Complete Binary Tree is just another kind of binary tree, its node structure is exactly the same as that of a binary tree.

We can define it as follows:

typedef struct node{
    int data;
    struct node *left;
    struct node *right;
    
}NODE;

So, as you can see, it consists of an element containing its own data, a left child pointer and a right child pointer.

The Insertion Process

This is the part where it differs from the logic of a basic Binary Tree.

As we're gonna fill it from left to right direction, we need to implement the logic accordingly in the code.

Step 1.

Our first task would be to create a new node containing the value that has to be inserted into the tree. We're gonna do that using the following "createNode" function.

NODE *createnode(int val){
    NODE *newnode = (NODE *)malloc(sizeof(NODE));
    newnode->data = val;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}

As you can see, first we allocate some block of memory for creating the node, then we simply assign the values for each of the node elements(data, right and left). Finally we return this node.

We're going to make use of this function in our next step where we create the function that implements the insertion of the node into the binary tree.

Step 2.

So now we're gonna make a function that inserts a node into the tree.

NODE *insertInTree(int val, NODE *root){
    NODE *newnode = createnode(val);
    if(root  == NULL){
        root = rootNode = newnode;
    }else{
        //root not empty
        if(root->left == NULL){//check if left is empty
            root->left = newnode;
        }else{
            if(root->right == NULL){//check if right is empty
                root->right = newnode;
            }else{
                //both right and left child are occupied
                
                //check if child nodes of left subtree are occupied or not
                if(root->left->left==NULL || root->left->right==NULL){
                    //if yes, then traverse to the left subtree
                    return insertInTree(val, root->left);
                }else if(root->right->left==NULL || root->right->right==NULL){
                    //if yes, traverse to the right subtree
                    return insertInTree(val, root->right);
                }else{
                    //if their child nodes are occupied too
                    //traverse to left of left of root NODE
                    return insertInTree(val, root->left->left);
                }
            }
        }
    }
    return root;
}

Through this piece of code -

  1. We create a node that contains a certain value that the user enters.
  2. Then we check if the root pointer is pointing at something or not -
    1. If it is not, then we simply assign the created node to the root node.
    2. Otherwise, we check if the root's children nodes are free.
  3. As we want to go from left to right direction while filling the tree -
    1. We first check for availability of left child node -
      1. If it is available, assign the new node to it.
      2. Otherwise, check if the Right child node is available -
        1. If it is, assign the new node to it.
        2. Otherwise, we have no other option but to explore the binary tree further, recursively to find an empty spot.
        3. For that we first check if the left child node has both its child nodes.
          1. If yes, do recursion with respect to the left child node.
          2. If not, check if the right child node has both its child nodes.
            1. If yes, do recursion with respect to the right child node.
            2. If not, then just start recursion with respect to the left of the left node to see if there are any empty spot(we start from the left end as the tree has to be filled from left to right side).
  4. At the end, return the root node.

The above process actually looks like this- COMPELETEbinaryTREE.gif

Full code

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

typedef struct node{
    int data;
    struct node *left;
    struct node *right;
}NODE;

NODE *rootNode = NULL;

NODE *createnode(int val){
    NODE *newnode = (NODE *)malloc(sizeof(NODE));
    newnode->data = val;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}

NODE *insertInTree(int val, NODE *root){
    NODE *newnode = createnode(val);
    if(root  == NULL){
        root = rootNode = newnode;
    }else{
        //root not empty
        if(root->left == NULL){//check if left is empty
            root->left = newnode;
        }else{
            if(root->right == NULL){//check if right is empty
                root->right = newnode;
            }else{
                //both right and left child are occupied
                
                //check if child nodes of left subtree are occupied or not
                if(root->left->left==NULL || root->left->right==NULL){
                    //if yes, then traverse to the left subtree
                    return insertInTree(val, root->left);
                }else if(root->right->left==NULL || root->right->right==NULL){
                    //if yes, traverse to the right subtree
                    return insertInTree(val, root->right);
                }else{
                    //if their child nodes are occupied too
                    //traverse to left of left of root NODE
                    return insertInTree(val, root->left->left);
                }
            }
        }
    }
    return root;
}

void inorder(NODE *root){
    if(root == NULL){
        return;
    }else{
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main(){
    //Insert
    int arr[6] = {3,9,2,1,4,5};
    for(int i=0; i<6; i++){
     insertInTree(arr[i], rootNode);   
    }
              
    printf("Inorder Traversal: ");
    inorder(rootNode);
                
    
}

Here in this code, I've directly used an array of 6 integers instead of getting inputs from the user.

An important thing to observe here is that I've introduced the "rootNode" pointer globally. If I had introduced it in the main function, by the end of the insertion process it would've ended up pointing at the lastly inserted element and we won't be able to used it for the traversal method later on in the main function. So, to not let that happen the rootNode was declared globally and we set it equal to the value of the root node, thereby using a different local variable in the insertion function as the root node variable.

Conclusion

I hope you got some clarity about Complete Binary Trees through this article. It is very important to know how complete binary trees work especially when you wanna learn the concept of heaps. In the upcoming articles, I'll try to relate the concept of complete binary trees with that of heaps and how it is implemented in C.

I hope you liked reading this article. For more such articles you can visit my page here.

Thanks for reading!✨