Home Trees Write a program for inserting an element into a binary tree

Write a program for inserting an element into a binary tree

by nikoo28
1 comment

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
tree_insert_element_1
Output: After insertion
tree_insert_element_2

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

You may also like

1 comment

joel sharma September 19, 2017 - 23:54

In line 39 why do we dequeue(q)?

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

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

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More