Insertion in a binary tree level order in C

Last Updated on July 4, 2024 by Abhishek Sharma

In computer science, binary trees are fundamental data structures used to represent hierarchical relationships. Insertion in a binary tree level order is a common operation that ensures the tree remains balanced, meaning all levels are filled as much as possible from left to right. This method of insertion is particularly useful in creating complete binary trees, where all levels are fully filled except possibly for the last level, which is filled from left to right. This guide will delve into the implementation of level order insertion in a binary tree using the C programming language, providing a clear and concise explanation along with sample code to illustrate the concept.

Understanding Binary Trees

Before we delve into the insertion process, let’s briefly review binary trees. A binary tree is a hierarchical data structure consisting of nodes, each having a maximum of two children, namely the left child and the right child. The topmost node in the tree is called the root node, and it serves as the starting point for traversing the tree. The children of a node are often referred to as its left and right subtrees.

Level Order Traversal

Level order traversal is a popular technique used to traverse a binary tree. It explores the tree level by level, starting from the root node and moving down to the subsequent levels. In this traversal, all the nodes at a particular level are visited before moving on to the next level. It ensures that the nodes are processed in a breadth-first manner.

Insertion in Binary Trees

To insert a new node into a binary tree using level order traversal, we follow a specific algorithm. Here is a step-by-step guide to performing the insertion:

1. Start with the root node of the binary tree.
2. If the root is NULL, create a new node with the given data and set it as the root node.
3. Otherwise, create a queue data structure to hold the nodes during traversal.
4. Enqueue the root node into the queue.
5. Repeat the following steps until the queue becomes empty:
   a. Dequeue a node from the front of the queue.
   b. Check if the left child of the dequeued node is NULL.
   • If so, create a new node with the given data and set it as the left child.
   • If not, enqueue the left child into the queue.
     c. Check if the right child of the dequeued node is NULL.
   • If so, create a new node with the given data and set it as the right child.
   • If not, enqueue the right child into the queue.
6. Once the queue is empty, the insertion process is complete.

C Implementation of Insertion in a binary tree level order

Let’s now implement the insertion algorithm in C, using the step-by-step guide mentioned above:

C Implementation of Insertion in a binary tree level order

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void insertLevelOrder(struct Node* root, int data) {
    // Create a queue for level order traversal
    struct Node** queue = (struct Node**)malloc(100 * sizeof(struct Node*));
    int front = 0;
    int rear = 0;

    // If the tree is empty, assign the data to the root
    if (root == NULL) {
        root = createNode(data);
        return;
    }

    // Enqueue the root node
    queue[rear++] = root;

    // Iterate through the tree using level order traversal
    while (front < rear) {
        struct Node* tempNode = queue[front++];

        // If the left child is empty, create a new node and assign the data
        if (tempNode->left == NULL) {
            tempNode->left = createNode(data);
            break;
        }
        // If the left child is not empty, enqueue it
        else {
            queue[rear++] = tempNode->left;
        }

        // If the right child is empty, create a new node and assign the data
        if (tempNode->right == NULL) {
            tempNode->right = createNode(data);
            break;
        }
        // If the right child is not empty, enqueue it
        else {
            queue[rear++] = tempNode->right;
        }
    }

    free(queue);
}

void levelOrderTraversal(struct Node* root) {
    // Create a queue for level order traversal
    struct Node** queue = (struct Node**)malloc(100 * sizeof(struct Node*));
    int front = 0;
    int rear = 0;

    // Enqueue the root node
    queue[rear++] = root;

    // Iterate through the tree using level order traversal
    while (front < rear) {
        struct Node* tempNode = queue[front++];
        printf("%d ", tempNode->data);

        // Enqueue the left child if it exists
        if (tempNode->left != NULL) {
            queue[rear++] = tempNode->left;
        }

        // Enqueue the right child if it exists
        if (tempNode->right != NULL) {
            queue[rear++] = tempNode->right;
        }
    }

    free(queue);
}

int main() {
    // Create the root node
    struct Node* root = createNode(1);

    // Perform insertions using level order traversal
    insertLevelOrder(root, 2);
    insertLevelOrder(root, 3);
    insertLevelOrder(root, 4);
    insertLevelOrder(root, 5);

    // Print the level order traversal
    printf("Level Order Traversal: ");
    levelOrderTraversal(root);

    return 0;
}

In the code snippet above, we define a structure Node to represent each node in the binary tree. The createNode() function creates a new node with the provided data. The insertLevelOrder() function performs the insertion using the level order traversal approach, following the algorithm we discussed earlier. The levelOrderTraversal() function prints the level order traversal of the binary tree. Finally, in the main() function, we create the root node and perform insertions to demonstrate the level order insertion. Finally, we print the level order traversal of the tree.

Conclusion
Level order insertion in a binary tree is a vital technique to ensure the tree remains balanced and efficient for various operations. By understanding and implementing this method in C, you can maintain the structural integrity of your binary tree, making it a robust and reliable data structure for your applications. The provided implementation and explanations aim to give you a solid foundation in mastering level order insertion in binary trees.

Frequently Asked Questions (FAQS) related to Insertion in a binary tree level order in C

Here are some FAQs related to Insertion in a binary tree level order in C:

Q1: What is a binary tree?
A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child.

Q2: What does level order insertion mean in a binary tree?
Level order insertion in a binary tree means adding a new node to the tree in such a way that all levels are filled from left to right before moving to the next level. This ensures that the tree remains balanced.

Q3: Why is level order insertion important?
Level order insertion is important because it maintains the tree’s balance, ensuring efficient performance for operations such as search, insert, and delete, which are crucial for many applications.

Q4: How do you implement level order insertion in a binary tree in C?
Level order insertion can be implemented using a queue to traverse the tree level by level until an appropriate position is found for the new node. The new node is then added as a left or right child of the current node.

Q5: What libraries are required for implementing a binary tree in C?
The standard libraries stdio.h and stdlib.h are typically used. stdio.h is used for input and output operations, while stdlib.h is used for memory allocation functions like malloc.