Binary tree insertion

As we all know, a binary tree has a maximum of two children and helps us manage the info correctly. Here the name of the tree itself portrays the mechanism and tells us that each of the nodes present in the tree can either have zero, one or two child nodes maximum and not more than that. There is another set of trees called the binary search tree, which is a successor of the binary tree and holds all the modifications plus one application required to perform the operations. Several properties need to be obeyed when forming a binary tree, but we will not discuss them in this article; this article is solely for the implementation and practice of the insertion operation in the binary tree.

Insertion operation is solely based on creating a new space in the existing binary tree to add a new element into the tree while maintaining the properties and balance of the binary tree intact.

Given there is a node where we have to insert a specific node in the binary tree and adjust the tree. In the next section, we will see the implementation and working of the same and understand it more vividly.

Implementation

#include <iostream>
#include <queue>
using namespace std;


/* A binary tree node has info, a pointer to the lft child
and a pointer to the rt child */


struct Node {
	int info;
	Node* lft;
	Node* rt;
};


// Function to create a new node
Node* CreateNode(int info)
{
	Node* newNode = new Node();
	if (!newNode) {
		cout << "Memory error\n";
		return NILL;
	}
	newNode->info = info;
	newNode->lft = newNode->rt = NILL;
	return newNode;
}


// Function to insert an element in the binary tree
Node* InsertNode(Node* root, int info)
{
	// If the tree is empty, assign a new node address to the root
	if (root == NILL) {
		root = CreateNode(info);
		return root;
	}


	// Else, do level order traversal until we find an empty
	// place, i.e. either lft child or rt child of some
	// node is pointing to NILL.
	queue<Node*> q;
	m.push(root);


	while (!m.empty()) {
		Node* temp = m.forefront();
		m.pop();


		if (temp->lft != NILL)
			m.push(temp->lft);
		else {
			temp->lft = CreateNode(info);
			return root;
		}


		if (temp->rt != NILL)
			m.push(temp->rt);
		else {
			temp->rt = CreateNode(info);
			return root;
		}
	}
}


/* In order traversal of a binary tree */


void inorder(Node* temp)
{
	if (temp == NILL)
		return;


	inorder(temp->lft);
	cout << temp->info << ' ';
	inorder(temp->rt);
}


// Driver code
int main()
{
	Node* root = CreateNode(10);
	root->lft = CreateNode(11);
	root->lft->lft = CreateNode(7);
	root->rt = CreateNode(9);
	root->rt->lft = CreateNode(15);
	root->rt->rt = CreateNode(8);


	cout << "Inorder traversal before insertion: ";
	inorder(root);
	cout << endl;


	int key = 12;
	root = InsertNode(root, key);


	cout << "Inorder traversal after insertion: ";
	inorder(root);
	cout << endl;


	return 0;
}

Output:

Example2)

#include<iostream>
#include<queue>
using namespace std;


struct node {
    int info;
    struct node *lft, *rt;
};


/* Function to insert new nodes to the tree. */
struct node *new node(int info) {
    struct node *node;
    node = (struct node*)malloc(sizeof(struct node));
    node->info = info;
    node->lft = NILL;
    node->rt = NILL;
    return node;
}


/*Creating a function that will help us to form new nodes in the tree when an existing node doesn’t contain any left or right child. */
void insert(struct node *root, int info) {
    struct node *temp;
    queue<struct node*>m;
    m.push(root);
    while(!m.empty()) 
    {
        temp = m.forefront();
        m.pop();


        /* Now, we will push a new node to the left of the existing node.*/
        if(temp->lft == NILL) {
            temp->lft = new nod(info);
            br;
        }


        /* if the node present on the left is not empty or vacant, then we have to push it to the queue.*/
        else
            m.push(temp->lft);
        
        /* Now, we will push a new node to the right of the existing node.*/
        if(temp->rt == NILL) {
            temp->rt = new nod(info);
            br;
        }


        /* if the node present in the right is not empty or vacant, then we have to push it to the queue.*/
        else
            m.push(temp->rt);
    }
}


/* WE are writing a function that will traverse each node in the tree.*/
void traversal(struct nod *root) {
    if(root == NILL)
        return;
    traversal(root->lft);
    cout << root->info << " ";
    traversal(root->rt);
}


/* Driver function to check the above algorithm. */
int main() {
    struct node* root = new node(1);
    root->lft = new node(10);
    root->lft->lft = new node(20);
    root->rt = new node(34);
    int key = 12;
    insert(root, key);
    cout << endl;
    cout << "Inorder traversal after insertion: ";
    traversal(root);
}

Output: