In my previous article, I covered all about Binary trees and it's different types. Well, that article was all theory, but important and necessary theory. But in this article, we will start with algorithms and programs related to a Binary tree.
So consider that you are given a binary tree and you have to insert a given node to it and then print all the tree elements in Inorder traversal.
Insertion in a Binary Tree Data Structure
Quick Think:
For inserting a node in a binary tree you will have to check the following conditions:
-
If a node in the binary tree does not have its left child, then insert the given node(the one that we have to insert) as its left child.
-
If a node in the binary tree does not have its right child then insert the given node as its right child.
-
If the above-given conditions do not apply then search for the node which does not have a child at all and insert the given node there.
-
We can use a queue for the implementation of this algorithm, as it is easy to store and retrieve the nodes of the binary tree that way because the queue follows the FIFO rule. Also, most of the tree algorithms are implemented using a queue.
Algorithm
Step 1: Create a function to insert the given node and pass two arguments to it, the root node and the data to be inserted.
Step 2: Define a temporary node to store the popped-out nodes from the queue for search purposes.
Step 3: Define a queue data structure to store the nodes of the binary tree.
Step 4: Push the root node inside the queue data structure.
Step 5: Start a while loop and check for the condition that whether the queue is empty or not, if not empty then go to Step 6, else go to Step 9.
Step 6: Pop out the first node from the queue and store it inside the temporary node.
Step 7: Check, for the current pooped-out node, in the binary tree, inside the while loop, if its left child(in binary tree) is null then call the memory allocation method for the new node, with its left and right child set as null and then insert the given node to its new position else push its left child in the queue data structure.
Step 8: Similarly repeat Step 7 for the right child of the current node in the binary tree.
Step 9: End of the while loop.
Step 10: End of the function.
Implementation of the above Algorithm
We will be writing the code in C++.
#include<iostream>
#include<queue>
using namespace std;
struct node {
int data;
struct node *left, *right;
};
/* Function to insert new nodes to the tree. */
struct node *newnode(int data) {
struct node *node;
node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
/* Function to insert the formed nodes to the tree when a parent node does not have a right or the left child. */
void insert(struct node *root, int data) {
struct node *temp;
queue<struct node*>q;
q.push(root);
while(!q.empty())
{
temp = q.front();
q.pop();
/* Insert node as the left child of the parent node. */
if(temp->left == NULL) {
temp->left = newnode(data);
break;
}
/* If the left node is not null push it to the queue. */
else
q.push(temp->left);
/* Insert node as the right child of the parent node. */
if(temp->right == NULL) {
temp->right = newnode(data);
break;
}
/* If the right node is not null push it to the queue. */
else
q.push(temp->right);
}
}
/* Function for tree traversal of every node in the tree. */
void traversal(struct node *root) {
if(root == NULL)
return;
traversal(root->left);
cout << root->data << " ";
traversal(root->right);
}
/* Driver function to check the above algorithm. */
int main() {
struct node* root = newnode(1);
root->left = newnode(10);
root->left->left = newnode(20);
root->right = newnode(34);
int key = 12;
insert(root, key);
cout << endl;
cout << "Inorder traversal after insertion: ";
traversal(root);
}
Output:
Inorder traversal after insertion: 20 10 12 1 34
In the section below we will step by step learn how the above code works.
Explanation of the Algorithm
Now let us consider a tree(depicted in the diagram below) where we have to insert a new node with value equal to 12. Now to insert the given key value we will run our written code:
The code execution begins with pushing the root node onto the queue, therefore the node with data value 1 is pushed onto the queue as shown in the diagram below:
Now, as the queue is not empty, hence the code provides a condition to the program that the operation of traversing each and every node in the tree should continue till there is no node left in the queue.
Then the top value of the node data present in the queue is stored in a struct node variable(temporary node) and the node data is popped out of the queue.
The popped out node data is then checked for having or not having a left child. Here from the given diagram, we can see that the top value has a left child so we will simply push the left child node data to the queue and the queue will look like this:
Similarly, we will check if the popped-out value of the queue(which is the root node in this case) if it has a right child or not, here we have the right child, so we will push the right child node data to the queue and the queue will look like this:
Since the queue is not empty so the loop will execute once more and similarly the top value of the node data present in the queue is stored in a struct node variable(temporary node) and the node data is popped out of the queue, leaving only 34 in the queue.
Now the popped-out value of the node is checked if it has a left child. Here from the given diagram, we can see that the node does not have the right child so we will simply allocate a new node with the data value of the key to be inserted into the tree and break the loop and the program is terminated with the result as:
Conclusion
Adding a new node to a binary tree is a fundamental operation in data structures and algorithms. The process involves traversing the tree to find the appropriate position for the new node, and then adjusting the tree structure accordingly. Understanding the principles behind insertion in a binary tree is essential for mastering more advanced tree-based algorithms.
By implementing efficient insertion techniques, we can optimize the performance of our binary tree applications and unlock new possibilities for solving complex problems. With patience and practice, anyone can become proficient in this important skill.
Frequently Asked Questions(FAQs)
1) How do you insert a new node in a binary tree in C?
To insert a new node in a binary tree in C, first, we need to find the appropriate position for the new node. We can traverse the tree in a pre-order, in-order, or post-order manner to find the position. Once we find the appropriate position, we can create a new node and add it as the left or right child of the parent node.
2) What is the time complexity of inserting a node in a binary tree in C?
The time complexity of inserting a node in a binary tree in C depends on the height of the tree. In the worst-case scenario, when the tree is completely unbalanced, the time complexity is O(n), where n is the number of nodes in the tree. In the best-case scenario, when the tree is perfectly balanced, the time complexity is O(log n).
3) Can a binary tree have duplicate nodes?
Yes, a binary tree can have duplicate nodes. However, it depends on the implementation. In some implementations, duplicates are not allowed, while in others, duplicates are allowed.
4) How do you handle duplicate nodes when inserting a new node in a binary tree in C?
When inserting a new node in a binary tree in C, if the new node is a duplicate of an existing node, we need to decide how to handle it. One approach is to discard the duplicate node and do nothing. Another approach is to update the value of the existing node to the value of the new node. It depends on the application and the requirements.
You may also like:
