Open In App

Deletion in a Binary Tree

Last Updated : 16 Mar, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

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

Examples :

Input : Delete 10 in below tree

       10
     /    \         
  20     30

Output:    
       30
     /             
 20     

Input : Delete 20 in below tree
       10
     /    \         
 20     30
            \
            40

Output:    
       10
   /      \             
40        30
            

Algorithm:

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

Below is the implementation of the above approach:

C++ 
// 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 */
Node* deletion(struct Node* root, int key)
{
    if (root == NULL)
        return NULL;

    if (root->left == NULL && root->right == NULL) {
        if (root->key == key)
            return NULL;
        else
            return root;
    }

    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);
    }

    if (key_node != NULL) {
        int x = temp->key;
          key_node->key = x;
        deletDeepest(root, temp);
    }
    return root;
}

// 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;
    root = deletion(root, key);

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

    return 0;
}
Java 
// Java program to delete element
// in binary tree
import java.util.LinkedList;
import java.util.Queue;

class GFG {

    // A binary tree node has key, pointer to
    // left child and a pointer to right child
    static class Node {
        int key;
        Node left, right;

        // Constructor
        Node(int key)
        {
            this.key = key;
            left = null;
            right = null;
        }
    }

    static Node root;
    static Node temp = root;

    // Inorder traversal of a binary tree
    static void inorder(Node temp)
    {
        if (temp == null)
            return;

        inorder(temp.left);
        System.out.print(temp.key + " ");
        inorder(temp.right);
    }

    // Function to delete deepest
    // element in binary tree
    static void deleteDeepest(Node root, Node delNode)
    {
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);

        Node temp = null;

        // Do level order traversal until last node
        while (!q.isEmpty()) {
            temp = q.peek();
            q.remove();

            if (temp == delNode) {
                temp = null;
                return;
            }
            if (temp.right != null) {
                if (temp.right == delNode) {
                    temp.right = null;
                    return;
                }
                else
                    q.add(temp.right);
            }

            if (temp.left != null) {
                if (temp.left == delNode) {
                    temp.left = null;
                    return;
                }
                else
                    q.add(temp.left);
            }
        }
    }

    // Function to delete given element
    // in binary tree
    static void delete(Node root, int key)
    {
        if (root == null)
            return;

        if (root.left == null && root.right == null) {
            if (root.key == key) {
                root = null;
                return;
            }
            else
                return;
        }

        Queue<Node> q = new LinkedList<Node>();
        q.add(root);
        Node temp = null, keyNode = null;

        // Do level order traversal until
        // we find key and last node.
        while (!q.isEmpty()) {
            temp = q.peek();
            q.remove();

            if (temp.key == key)
                keyNode = temp;

            if (temp.left != null)
                q.add(temp.left);

            if (temp.right != null)
                q.add(temp.right);
        }

        if (keyNode != null) {
            int x = temp.key;
              keyNode.key = x;
            deleteDeepest(root, temp);
        }
    }

    // Driver code
    public static void main(String args[])
    {
        root = new Node(10);
        root.left = new Node(11);
        root.left.left = new Node(7);
        root.left.right = new Node(12);
        root.right = new Node(9);
        root.right.left = new Node(15);
        root.right.right = new Node(8);

        System.out.print("Inorder traversal "
                         + "before deletion:");
        inorder(root);

        int key = 11;
        delete(root, key);

        System.out.print("\nInorder traversal "
                         + "after deletion:");
        inorder(root);
    }
}

// This code is contributed by Ravi Kant Verma
C# 
// C# program to delete element
// in binary tree

using System;
using System.Collections.Generic;

class GFG {

    // A binary tree node has key, pointer to
    // left child and a pointer to right child
    public class Node {
        public int key;
        public Node left, right;

        // Constructor
        public Node(int key)
        {
            this.key = key;
            left = null;
            right = null;
        }
    }

    static Node root;

    // Inorder traversal of a binary tree
    static void inorder(Node temp)
    {
        if (temp == null)
            return;

        inorder(temp.left);
        Console.Write(temp.key + " ");
        inorder(temp.right);
    }

    // Function to delete deepest
    // element in binary tree
    static void deleteDeepest(Node root, Node delNode)
    {
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);

        Node temp = null;

        // Do level order traversal until last node
        while (q.Count != 0) {
            temp = q.Peek();
            q.Dequeue();

            if (temp == delNode) {
                temp = null;
                return;
            }
            if (temp.right != null) {
                if (temp.right == delNode) {
                    temp.right = null;
                    return;
                }

                else
                    q.Enqueue(temp.right);
            }

            if (temp.left != null) {
                if (temp.left == delNode) {
                    temp.left = null;
                    return;
                }
                else
                    q.Enqueue(temp.left);
            }
        }
    }

    // Function to delete given element
    // in binary tree
    static void delete(Node root, int key)
    {
        if (root == null)
            return;

        if (root.left == null && root.right == null) {
            if (root.key == key) {
                root = null;
                return;
            }
            else
                return;
        }

        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);
        Node temp = null, keyNode = null;

        // Do level order traversal until
        // we find key and last node.
        while (q.Count != 0) {
            temp = q.Peek();
            q.Dequeue();

            if (temp.key == key)
                keyNode = temp;

            if (temp.left != null)
                q.Enqueue(temp.left);

            if (temp.right != null)
                q.Enqueue(temp.right);
        }

        if (keyNode != null) {
            int x = temp.key;
            keyNode.key = x;
            deleteDeepest(root, temp);
        }
    }

    // Driver code
    public static void Main(String[] args)
    {
        root = new Node(10);
        root.left = new Node(11);
        root.left.left = new Node(7);
        root.left.right = new Node(12);
        root.right = new Node(9);
        root.right.left = new Node(15);
        root.right.right = new Node(8);

        Console.Write("Inorder traversal "
                      + "before deletion: ");
        inorder(root);

        int key = 11;
        delete(root, key);

        Console.Write("\nInorder traversal "
                      + "after deletion: ");
        inorder(root);
    }
}

// This code is contributed by Abhijeet Kumar(abhijeet19403)
Javascript 
<script>
    // Javascript program to delete element in binary tree
    
    class Node
    {
        constructor(key) {
           this.left = null;
           this.right = null;
           this.key = key;
        }
    }
    
    let root;
    let temp = root;

    // Inorder traversal of a binary tree
    function inorder(temp)
    {
        if (temp == null)
            return;

        inorder(temp.left);
        document.write(temp.key + " ");
        inorder(temp.right);
    }

    // Function to delete deepest
    // element in binary tree
    function deleteDeepest(root, delNode)
    {
        let q = [];
        q.push(root);

        let temp = null;

        // Do level order traversal until last node
        while (q.length > 0)
        {
            temp = q[0];
            q.shift();

            if (temp == delNode)
            {
                temp = null;
                return;

            }
            if (temp.right!=null)
            {
                if (temp.right == delNode)
                {
                    temp.right = null;
                    return;
            }
            else
                q.push(temp.right);
        }

        if (temp.left != null)
        {
            if (temp.left == delNode)
            {
                temp.left = null;
                return;
            }
            else
                q.push(temp.left);
        }
    }
    }

    // Function to delete given element
    // in binary tree
    function Delete(root, key)
    {
        if (root == null)
            return;

        if (root.left == null &&
           root.right == null)
        {
            if (root.key == key)
            {
                  root=null;
                  return;
            }
            else
                return;
        }

        let q = [];
        q.push(root);
        let temp = null, keyNode = null;

        // Do level order traversal until
        // we find key and last node.
        while (q.length > 0)
        {
            temp = q[0];
            q.shift();

            if (temp.key == key)
                keyNode = temp;

            if (temp.left != null)
                q.push(temp.left);

            if (temp.right != null)
                q.push(temp.right);
        }

        if (keyNode != null)
        {
            let x = temp.key;
            keyNode.key = x;
            deleteDeepest(root, temp);
        }
    }
    
    root = new Node(10);
    root.left = new Node(11);
    root.left.left = new Node(7);
    root.left.right = new Node(12);
    root.right = new Node(9);
    root.right.left = new Node(15);
    root.right.right = new Node(8);
 
    document.write("Inorder traversal " +
                     "before deletion: ");
    inorder(root);
 
    let key = 11;
    Delete(root, key);
 
    document.write("</br>" + "Inorder traversal " +
                     "after deletion: ");
    inorder(root);

</script>
Python3 
# Python3 program to illustrate deletion in a Binary Tree

# class to create a node with data, left child and right child.


class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Inorder traversal of a binary tree


def inorder(temp):
    if(not temp):
        return
    inorder(temp.left)
    print(temp.data, end=" ")
    inorder(temp.right)

# function to delete the given deepest node (d_node) in binary tree


def deleteDeepest(root, d_node):
    q = []
    q.append(root)
    while(len(q)):
        temp = q.pop(0)
        if temp is d_node:
            temp = None
            return
        if temp.right:
            if temp.right is d_node:
                temp.right = None
                return
            else:
                q.append(temp.right)
        if temp.left:
            if temp.left is d_node:
                temp.left = None
                return
            else:
                q.append(temp.left)

# function to delete element in binary tree


def deletion(root, key):
    if root == None:
        return None
    if root.left == None and root.right == None:
        if root.key == key:
            return None
        else:
            return root
    key_node = None
    q = []
    q.append(root)
    temp = None
    while(len(q)):
        temp = q.pop(0)
        if temp.data == key:
            key_node = temp
        if temp.left:
            q.append(temp.left)
        if temp.right:
            q.append(temp.right)
    if key_node:
        x = temp.data
        key_node.data = x
        deleteDeepest(root, temp)
    return root


# Driver code
if __name__ == '__main__':
    root = Node(10)
    root.left = Node(11)
    root.left.left = Node(7)
    root.left.right = Node(12)
    root.right = Node(9)
    root.right.left = Node(15)
    root.right.right = Node(8)
    print("The tree before the deletion: ", end = "")
    inorder(root)
    key = 11
    root = deletion(root, key)
    print();
    print("The tree after the deletion: ", end = "")
    inorder(root)

# This code is contributed by Monika Anandan

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

Time complexity: O(n) where n is no number of nodes
Auxiliary Space: O(n) size of queue

Note: We can also replace the 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.



https://media.geeksforgeeks.org/auth/avatar.png
GeeksforGeeks
Improve
Previous Article
Insertion in a Binary Tree in level order
Next Article
Enumeration of Binary Trees

Similar Reads

Deletion of a given node K in a Binary Tree using Level Order Traversal
Given a binary tree and a node K, the task is to delete the node K from it by making sure that tree shrinks from the bottom (i.e. the deleted node is replaced by bottom-most and rightmost node) using Level Order Traversal. Examples: Input: K = 8, Tree = Output: Explanation: Please Refer below for explanation. Input: K = 1, Tree = Output: Approach:
13 min read
Threaded Binary Search Tree | Deletion
A threaded binary tree node looks like following. C/C++ Code struct Node { struct Node *left, *right; int info; // false if left pointer points to predecessor // in Inorder Traversal bool lthread; // false if right pointer points to predecessor // in Inorder Traversal bool rthread; }; Java Code static class Node { Node left, right; int info; // Tru
15+ min read
Deletion in Binary Search Tree (BST)
Given a BST, the task is to delete a node in this BST, which can be broken down into 3 scenarios: Case 1. Delete a Leaf Node in BST Case 2. Delete a Node with Single Child in BSTDeleting a single child node is also simple in BST. Copy the child to the node and delete the node.  Case 3. Delete a Node with Both Children in BSTDeleting a node with bot
15 min read
Complexity of different operations in Binary tree, Binary Search Tree and AVL tree
In this article, we will discuss the complexity of different operations in binary trees including BST and AVL trees. Before understanding this article, you should have a basic idea about Binary Tree, Binary Search Tree, and AVL Tree. The main operations in a binary tree are: search, insert and delete. We will see the worst-case time complexity of t
4 min read
Convert a Binary Tree into its Mirror Tree (Invert Binary Tree)
Given a binary tree, the task is to convert the binary tree into its Mirror tree. Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged. Recommended PracticeMirror TreeTry It!The idea is to traverse recursively and swap the right and left subtrees after traversing the subtrees. Follow
15+ min read
m-Way Search Tree | Set-2 | Insertion and Deletion
Insertion in an m-Way search tree: The insertion in an m-Way search tree is similar to binary trees but there should be no more than m-1 elements in a node. If the node is full then a child node will be created to insert the further elements. Let us see the example given below to insert an element in an m-Way search tree.Example: To insert a new el
15+ min read
Minimize deletion of edges to convert Tree into a forest of size at most N/2
Given a tree with N nodes, numbered from 0 to N - 1, the task is to find the minimum number of deletion of edges, such that, the tree is converted into a forest where each tree in the forest can have size less than equal to ⌊N/2⌋. Examples: Input: N = 3, edges = [[0, 1], [0, 2]] 0 / \ 1 2Output: 2Explanation: The maximum size of each tree after rem
14 min read
Van Emde Boas Tree | Set 4 | Deletion
It is highly recommended to read the previous articles on Van Emde Boas Tree first. Procedure for Delete: Here we are assuming that the key is already present in the tree. First we check if only one key is present, then assign the maximum and minimum of the tree to null value to delete the key.Base Case: If the universe size of the tree is two then
15+ min read
Deletion in an AVL Tree
We have discussed AVL insertion in the previous post. In this post, we will follow a similar approach for deletion. Steps to follow for deletion. To make sure that the given tree remains AVL after every deletion, we must augment the standard BST delete operation to perform some re-balancing. Following are two basic operations that can be performed
15+ min read
Deletion in Red-Black Tree
Deletion in a red-black tree is a bit more complicated than insertion. When a node is to be deleted, it can either have no children, one child or two children. Here are the steps involved in deleting a node in a red-black tree:If the node to be deleted has no children, simply remove it and update the parent node.If the node to be deleted has only o
15+ min read
Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox