Delete the Element from the Binary Tree Using C#

Binary Tree

A tree whose elements have at most two children is called a binary tree. Since each element in a binary tree can have a maximum of 2 children, we typically name them the left and right child. So, in a binary tree, a node contains a data element (for simplicity, taken as int datatype), left node, and right node.

The topmost node is called the root of the tree.

Let's start by creating a tree for the main function. So here, in the example below, we have 50 as our root node and 30 & 70 as his left and right children. Similarly, 20 and 40 are the left and right child of 30. Nodes that don't have any child are called leaf nodes, so in this below example 20, 40, 60, and 80 are our leaf nodes.

Here is the main method, we have created the object of the tree class and assigned 50 to his root node and assigned 30 and 70 to the left and right nodes of 50, respectively. Similarly, we have created the left and right nodes of respective nodes.

So, to delete any element from the binary tree, we need to follow the below algorithm.

1. Starting at the root, find the node that we want to delete.
2. Find the deepest node in the tree.
3. Replace the deepest node data with the node to be deleted.
4. Then, delete the deepest node.

So, we are going to create a function that will iterate through all the elements and delete the element matching with the passing key.

Below is the delete method, which takes the root node as the first parameter and the element to delete i.e. key as the second parameter. Here, we are using a queue data structure to iterate through tree level-wise. Once we iterated through all the nodes, at end, temp will be pointing to our deepest node i.e. 80 in the above example, and we are copying the value of that node to our node to change. After that, the last step is to select the deepest node, so here we are calling the deletedeepest function, which takes the root node as the first parameter and the node to delete i.e. temp as the second parameter.

Below is the implementation of the deletedeepest function.

So, our main function at the end will be,

Console Output

Here, the -20 element is replaced with the deepest element i.e. 80.

Full Code

using System;
using System.Collections.Generic;

class Tree
{
    Node root;

    class Node
    {
        public int data;
        public Node left, right;

        public Node(int i)
        {
            data = i;
            left = right = null;
        }
    }

    void PrintPre(Node root)
    {
        if (root == null)
            return;

        Console.Write(root.data + " ");
        PrintPre(root.left);
        PrintPre(root.right);
    }

    // Function to delete the given deepest node
    void DeleteDeepest(ref Node root, Node toDelete)
    {
        Node temp;
        Queue<Node> q1 = new Queue<Node>();
        q1.Enqueue(root);

        while (q1.Count != 0)
        {
            temp = q1.Dequeue();

            if (temp == toDelete) // If contains only single element and that needs to be deleted
            {
                root = null;
                break;
            }

            if (temp.left != null)
            {
                if (temp.left == toDelete)
                {
                    temp.left = null;
                    return;
                }
                q1.Enqueue(temp.left);
            }

            if (temp.right != null)
            {
                if (temp.right == toDelete)
                {
                    temp.right = null;
                    return;
                }
                q1.Enqueue(temp.right);
            }
        }
    }

    /* Function to delete element in binary tree */
    void Delete(ref Node root, int key)
    {
        Node temp, nodeToChange; // temp to store the current element and nodeToChange stores the element to delete.
        temp = nodeToChange = null;

        Queue<Node> q1 = new Queue<Node>();
        q1.Enqueue(root);

        while (q1.Count != 0)
        {
            temp = q1.Dequeue();

            if (temp.data == key)
            {
                nodeToChange = temp;
            }

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

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

        if (nodeToChange != null)
        {
            // After iterating from all the nodes, temp will be pointing to the deepest element of the tree.
            nodeToChange.data = temp.data; // Replace the deepest node data with the node to be deleted.
            DeleteDeepest(ref root, temp); // Delete the deepest node.
        }
    }

    public static void Main()
    {
        Tree t1 = new Tree();
        t1.root = new Node(50);
        t1.root.left = new Node(30);
        t1.root.right = new Node(70);
        t1.root.left.left = new Node(-20);
        t1.root.left.right = new Node(40);
        t1.root.right.left = new Node(60);
        t1.root.right.right = new Node(80);

        t1.PrintPre(t1.root); // Print elements in preOrder before deletion
        t1.Delete(ref t1.root, -20); // Delete element -20 from tree

        Console.WriteLine();
        t1.PrintPre(t1.root); // Print elements after deletion
    }
}