Write a program for inserting an element into a binary tree

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