Data Structures in C# - Exploring BinaryTree - Part 2 - Delete Node

Screenshot from the tutorial

Data Structures in C# - Exploring BinaryTree: Part 2 - Delete Node

Welcome back to our series on data structures in C#! In our previous post, we delved into the basics of binary trees, understanding their structure and how to implement them. Today, we will tackle a crucial operation within a binary tree: deleting a node.

Understanding Binary Trees

Before we jump into the deletion process, let's briefly recap what a binary tree is. A binary tree is a hierarchical structure in which each node has at most two children, referred to as the left and right child. This structure is widely used in various applications, including searching, sorting, and hierarchical data representation.

Why Delete a Node?

Deleting a node from a binary tree can be necessary for various reasons, such as maintaining tree balance, managing memory, or simply removing unwanted data. However, the deletion process is not as straightforward as adding a node. Depending on the node's position and its children, the deletion process can vary.

Deletion Scenarios

When deleting a node from a binary tree, we consider three main scenarios:

1. Node to be deleted is a leaf node: This is the simplest case where the node has no children. We can simply remove it.

2. Node to be deleted has one child: If the node has only one child, we will replace the node with its child.

3. Node to be deleted has two children: This is the most complex scenario. We typically find the node's inorder successor (the smallest node in the right subtree) or its inorder predecessor (the largest node in the left subtree) to replace the deleted node.

Implementing Node Deletion

Let’s explore how to implement the deletion of a node in C#. Below is the complete code for a BinaryTree class with a method to delete a node.

BinaryTree Class Code

public class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

public class BinaryTree
{
    public Node Root;

    public BinaryTree()
    {
        Root = null;
    }

    public Node DeleteNode(Node root, int value)
    {
        // Base case: If the tree is empty
        if (root == null)
        {
            return root;
        }

        // Recur down the tree to find the node to delete
        if (value < root.Value)
        {
            root.Left = DeleteNode(root.Left, value);
        }
        else if (value > root.Value)
        {
            root.Right = DeleteNode(root.Right, value);
        }
        else
        {
            // Node with only one child or no child
            if (root.Left == null)
                return root.Right;
            else if (root.Right == null)
                return root.Left;

            // Node with two children: Get the inorder successor
            Node temp = MinValueNode(root.Right);
            root.Value = temp.Value;
            root.Right = DeleteNode(root.Right, temp.Value);
        }
        return root;
    }

    private Node MinValueNode(Node node)
    {
        Node current = node;

        // Loop down to find the leftmost leaf
        while (current.Left != null)
        {
            current = current.Left;
        }
        return current;
    }
}

Explanation of the Code

• Node Class: Represents a single node in our binary tree, containing its value and pointers to the left and right children.

• BinaryTree Class: Contains the root node and methods to manipulate the tree, including the DeleteNode method.

• DeleteNode Method:

  • It first checks if the root is null, meaning the tree is empty.
  • It then searches for the node to delete by comparing values.
  • If found, it handles the three scenarios mentioned earlier:
    • If the node has no children, it simply returns null.
    • If the node has one child, it returns the child.
    • If the node has two children, it finds the inorder successor, replaces the node's value, and recursively deletes the successor.

• MinValueNode Method: This helper function finds the node with the smallest value in a given subtree, essential for deleting a node with two children.

Conclusion

Deleting nodes from a binary tree is an essential operation that can impact the overall structure and functionality of the tree. In this post, we explored the deletion process in depth, covering various scenarios and providing a practical implementation in C#.

Understanding how to delete nodes will help you manage binary trees effectively, ensuring optimal performance for operations like searching and inserting.

Stay tuned for the next part of our series, where we will explore more advanced operations in binary trees and other data structures in C#! If you have any questions or need further clarification, feel free to leave a comment below. Happy coding!

Another view from the tutorial

---

Connect with SkillBakery Studios

Explore more tutorials, tools, and resources:

• skillbakery.com
• Facebook
• X (Twitter)
• YouTube Channel

Posted by SkillBakery Studios