Question: Given the root pointer to a binary tree, write a program to insert an element in it.
Input: Sample Tree (Pointer to node 1 is given), Insert 7
Output: After insertion
We are given a binary tree with random allocated values and the pointer to the root node is given. Since the given tree is a binary tree, we can insert the element wherever we want. The only property of binary tree is that every node can have a maximum of two children. So, to keep the tree leveled we can perform a level order traversal on the binary tree and insert the element wherever we find the node whose right child or left child is NULL.
In the above example, while we are doing a level order traversal as soon as we come across node 3, we see that its left child is NULL. So we insert the new node to the left of node 3.
Here is an implementation of the above approach.
#include<stdio.h>
#include<malloc.h>
struct binaryTreeNode{
int data;
struct binaryTreeNode * left;
struct binaryTreeNode * right;
};
// A function to insert a number in a binary tree
// Parameters - the root node and the number to insert
struct binaryTreeNode * insertInBinaryTree(struct binaryTreeNode * root, int num)
{
struct binaryTreeNode * temp = NULL;
struct queue * Q = NULL;
// Create a new node to insert
struct binaryTreeNode * newNode = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
// Assign the values to this new node
newNode -> data = num;
newNode -> left = NULL;
newNode -> right = NULL;
if(root == NULL)
{
// If the root is NULL then the newNode is inserted at root
root = newNode;
return root;
}
// else proceed wiht the level order traversal
Q = enQueue(Q, root);
while(!isQueueEmpty(Q))
{
temp = Q -> front -> data;
Q = deQueue(Q);
// Now we have a node of the tree in temp
// If its left is empty we insert the node else we enqueue its
if(temp -> left != NULL)
{
Q = enQueue(Q, temp -> left);
}
else
{
// Assign the new node to its left
temp -> left = newNode;
// Delete the queue and return
free(Q);
return root;
}
// Do the same for the right sub-tree of the traversed node
if(temp -> right != NULL)
{
Q = enQueue(Q, temp -> right);
}
else
{
// Assign the node to its right
temp -> right = newNode;
// Delete the queue and return
free(Q);
return root;
}
}
free(Q);
return root;
}
Time Complexity:- O(n)
Space Complexity:- O(n)
Ideone link for the running program:- http://ideone.com/CFeFKF