Tutorialspoint.dev

Deletion in a Binary Tree

Given a binary tree, delete a node from it by making sure that tree shrinks from the bottom (i.e. the deleted node is replaced by bottom most and rightmost node). This different from BST deletion. Here we do not have any order among elements, so we replace with last element.

Examples :

Delete 10 in below tree
       10
     /             
    20     30
Output :    
       30
     /             
    20     


Delete 20 in below tree
       10
     /             
    20     30
            
            40
Output :    
       10
     /                
    40    30   



Algorithm
1. Starting at root, find the deepest and rightmost node in binary tree and node which we want to delete.
2. Replace the deepest rightmost node’s data with node to be deleted.
3. Then delete the deepest rightmost node.

// C++ program to delete element in binary tree
#include <bits/stdc++.h>
using namespace std;
  
/* A binary tree node has key, pointer to left
   child and a pointer to right child */
struct Node
{
    int key;
    struct Node* left, *right;
};
  
/* function to create a new node of tree and
   return pointer */
struct Node* newNode(int key)
{
    struct Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
};
  
/* Inorder traversal of a binary tree*/
void inorder(struct Node* temp)
{
    if (!temp)
        return;
    inorder(temp->left);
    cout << temp->key << " ";
    inorder(temp->right);
}
  
/* function to delete the given deepest node
   (d_node) in binary tree */
void deletDeepest(struct Node *root,
                  struct Node *d_node)
{
    queue<struct Node*> q;
    q.push(root);
  
    // Do level order traversal until last node
    struct Node* temp;
    while(!q.empty())
    {
        temp = q.front();
        q.pop();
        if(temp == d_node)
        {
            temp = NULL;
            delete(d_node);
            return;
        }
        if (temp->right)
        {
            if (temp->right == d_node)
            {
                temp->right = NULL;
                delete(d_node);
                return;
            }
            else
                q.push(temp->right);
        }
  
        if (temp->left)
        {
            if (temp->left == d_node)
            {
                temp->left=NULL;
                delete(d_node);
                return;
            }
            else
                q.push(temp->left);
        }
    }
}
  
/* function to delete element in binary tree */
void deletion(struct Node* root, int key)
{
    queue<struct Node*> q;
    q.push(root);
  
    struct Node *temp;
    struct Node *key_node = NULL;
  
    // Do level order traversal to find deepest
    // node(temp) and node to be deleted (key_node)
    while (!q.empty())
    {
        temp = q.front();
        q.pop();
  
        if (temp->key == key)
            key_node = temp;
  
        if (temp->left)
            q.push(temp->left);
  
        if (temp->right)
            q.push(temp->right);
    }
  
    int x = temp->key;
    deletDeepest(root, temp);
    key_node->key = x;
}
  
// Driver code
int main()
{
    struct Node* root = newNode(10);
    root->left = newNode(11);
    root->left->left = newNode(7);
    root->left->right = newNode(12);
    root->right = newNode(9);
    root->right->left = newNode(15);
    root->right->right = newNode(8);
  
    cout << "Inorder traversal before deletion : ";
    inorder(root);
  
    int key = 11;
    deletion(root, key);
  
    cout << endl;
    cout << "Inorder traversal after deletion : ";
    inorder(root);
  
    return 0;
}

Output:

Inorder traversal before deletion : 7 11 12 10 15 9 8 
Inorder traversal after deletion : 7 8 12 10 15 9 

Note: We can also replace node’s data that is to be deleted with any node whose left and right child points to NULL but we only use deepest node in order to maintain the Balance of a binary tree.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

tags:

Tree Tree

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter