Insertion Operation in a Binary Tree

In the previous article, we learned about the Representation and Traversal of Binary Tree in Data Structures, In this article, we will learn about the Insertion in Binary Tree in Data Structures.

968

Insertion operation is used to insert an element in a binary tree at the desired location.

An element can only be inserted in a binary tree if the appropriate location is found. Therefore, the given element which is to be inserted is first compared with the root node. If the element is less than the root node then it is compared with the right child of the root node. In the same way, the element is compared in either of the subtrees until the desired location is found.

An insertion in a binary tree involves the following steps –

  • Allocate the memory for the tree.
  • Set the data part to the value and set the left and right pointers of the tree, point to NULL.
  • If the item to be inserted, will be the first element of the tree, then the left and right of this node will point to NULL.
  • Else, check if the item is less than the root element of the tree, if this is true, then recursively perform this operation with the left of the root.
  • If this is false, then perform this operation recursively with the right sub-tree of the root.

Also check: spanning tree in data structure

Given below, is the algorithm for designing the insertion function for a binary tree –

IF TREE = NULL

    Allocate memory for TREE

   SET TREE -> DATA = ITEM

  SET TREE -> LEFT = TREE -> RIGHT = NULL

  ELSE

   IF ITEM < TREE -> DATA

    Insert(TREE -> LEFT, ITEM)

  ELSE

   Insert(TREE -> RIGHT, ITEM)

  [END OF IF]

  [END OF IF]

END

Now, we will see the code for this

Insertion operation in a Binary Tree –

#include<stdio.h>  

#include<stdlib.h>  

void insert(int);  

struct node  



    int data;  

    struct node *left;   

    struct node *right;   

};  

struct node *root;  

void main ()  



    int choice,item;  

    do   

    {  

        printf("\nEnter the item which you want to insert?\n");  

        scanf("%d",&item);  

        insert(item);  

        printf("\nPress 0 to insert more ?\n");  

        scanf("%d",&choice);  

    }while(choice == 0);  



void insert(int item)  



    struct node *ptr, *parentptr , *nodeptr;  

    ptr = (struct node *) malloc(sizeof (struct node));  

    if(ptr == NULL)  

    {  

        printf("can't insert");  

    }  

    else   

    {  

    ptr -> data = item;  

    ptr -> left = NULL;  

    ptr -> right = NULL;   

    if(root == NULL)  

    {  

        root = ptr;  

        root -> left = NULL;  

        root -> right = NULL;  

    }  

    else   

    {  

        parentptr = NULL;  

        nodeptr = root;   

        while(nodeptr != NULL)  

        {  

            parentptr = nodeptr;   

            if(item < nodeptr->data)  

            {  

                nodeptr = nodeptr -> left;   

            }   

            else   

            {  

                nodeptr = nodeptr -> right;  

            }  

        }  

        if(item < parentptr -> data)  

        {  

            parentptr -> left = ptr;   

        }  

        else   

        {  

            parentptr -> right = ptr;   

        }  

    }  

    printf("Node Inserted");  

    }  

Also check: max heap deletion algorithm

Try Free Data Structures MCQ Test

Previous QuizRepresentation and traversal techniques of Binary Tree
Next QuizDeletion in a Binary Tree

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.