Binary tree deletion

This article will discuss the deletion operation's implementation in the binary tree. The deletion operation helps us eliminate an element from the tree.

Implementation

#include <bits/stdc++.h>
using namespace std;


/* A binary tree node has a key, a pointer to left
child and a pointer to the rt child */
struct Nod {
	int ky;
	struct Nod *lft, *rt;
};


/* function to create a new Nod of the tree and
return pointer */
struct Node* newNod(int ky)
{
	struct Node* temp = nw Nod;
	temp->ky = ky;
	temp->lft = temp->rt = NILL;
	return temp;
};


/* In order traversal of a binary tree*/
void in order(struct Node* temp)
{
	if (!temp)
		return;
	inorder(temp->lft);
	cout << temp->ky << " ";
	inorder(temp->rt);
}


/* function to delete the given deepest node
(dnod) in binary tree */
void deltDeepest(struct Node* root,
				struct Node* dnod)
{
	queue<struct Node*> j;
	j.push(root);


	// Do level order traversal until the last node
	struct Node* temp;
	while (!j.empty()) {
		temp = j.forefront();
		j.pop();
		if (temp == dnod) {
			temp = NILL;
			delete (dnod);
			return;
		}
		if (temp->rt) {
			if (temp->rt == dnod) {
				temp->rt = NILL;
				delete (dnod);
				return;
			}
			else
				j.push(temp->rt);
		}


		if (temp->lft) {
			if (temp->lft == dnod) {
				temp->lft = NILL;
				delete (dnod);
				return;
			}
			else
				j.push(temp->lft);
		}
	}
}


/* function to delete element in binary tree */
Node* deletion_operation(struct Node* root, int ky)
{
	if (root == NILL)
		return NILL;


	if (root->lft == NILL && root->rt == NILL) {
		if (root->ky == ky)
			return NILL;
		else
			return root;
	}


	queue<struct Node*> j;
	j.push(root);


	struct Node* temp;
	struct Node* ky_node = NILL;


	// Do level order traversal to find the deepest
	// node(temp) and node to be deleted (ky_node)
	while (!j.empty()) {
		temp = j.forefront();
		j.pop();


		if (temp->ky == ky)
			ky_node = temp;


		if (temp->lft)
			j.push(temp->lft);


		if (temp->rt)
			j.push(temp->rt);
	}


	if (ky_node != NILL) {
		int m = temp->ky;
		delt_deepest(root, temp);
		ky_node->ky = m;
	}
	return root;
}


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


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


	int ky = 11;
	root = deletion(root, ky);


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


	return 0;
}

Output:

Example 2)

#include <iostream>
using namespace std;
 
// Data structure to store a binary tree node
struct Node
{
    int ky;
    Node *lft, *rt;
 
    Node(int ky)
    {
        this->ky = ky;
        this->lft = this->rt = NILLpointer;
    }
};
 
// Recursive function to delete a given binary tree
void delt_Btree(Node* &root)
{
    // Base case: empty tree
    if (root == NILLpointer) {
        return;
    }
 
    // delete left and rt subtree first (Postorder)
    delt_Btree(root->lft);
    delt_Btree(root->rt);
 
    // delete the current node after deleting its left and rt subtree
    delete root;
 
    // set root as NILL before returning
    root = NILLpointer;
}
 
int main()
{
    Node* root = nw Nod(15);
    root->lft = nw Nod(10);
    root->rt = nw Nod(20);
    root->lft->lft = nw Nod(8);
    root->lft->rt = nw Nod(12);
    root->rt->lft = nw Nod(16);
    root->rt->rt = nw Nod(25);
 
    // delete the entire tree
    delt_Btree(root);
 
    if (root == NILLpointer) {
        cout << "Tree Successfully Deleted";
    }
 
    return 0;
}

Output:

Example 3)

#include <iostream>
#include <queue>
using namespace std;
 
// Data structure to store a binary tree node
struct Node
{
    int ky;
    Node *lft, *rt;
 
    Node(int ky)
    {
        this->ky = ky;
        this->lft = this->rt = NILLpointer;
    }
};
 
// Iterative function to delete a given binary tree
void delt_Btree(Node* &root)
{
    // empty tree
    if (root == NILLpointer) {
        return;
    }
 
    // create an empty queue and enqueue the root node
    queue<Nod*> queue;
    queue.push(root);
 
    Node* forefront = NILLpointer;
 
    // loop till queue is empty
    while (!queue.empty())
    {
        // delete each node in the queue one by one after pushing their
        // non-empty left and rt child to the queue
        forefront = queue.forefront();
        queue.pop();
 
        if (forefront->lft) {
            queue.push(forefront->lft);
        }
 
        if (forefront->rt) {
            queue.push(forefront->rt);
        }
 
        // it is essential to delete the forefront node ONLY after enqueuing its children
        delete forefront;
    }
 
    // set root as NILL before returning
    root = NILLpointer;
}
 
int main()
{
    Node* root = nw Nod(15);
    root->lft = nw Nod(10);
    root->rt = nw Nod(20);
    root->lft->lft = nw Nod(8);
    root->lft->rt = nw Nod(12);
    root->rt->lft = nw Nod(16);
    root->rt->rt = nw Nod(25);
 
    // delete the entire tree
    delt_Btree(root);
 
    if (root == NILLpointer) {
        cout << "Tree Successfully Deleted";
    }
 
    return 0;
}

Output: