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

## 1 comment

In line 39 why do we dequeue(q)?