BST Delete Operation in DSA C# - Build from Scratch

BST Delete Operation

📖 Scenario: You are managing a collection of unique numbers using a Binary Search Tree (BST). Sometimes, you need to remove a number from this collection while keeping the BST rules intact.

🎯 Goal: Build a program that creates a BST, sets a value to delete, performs the delete operation correctly, and then prints the BST in order to show the updated tree.

📋 What You'll Learn

Create a BST with specific nodes

Set a variable for the value to delete

Implement the BST delete operation for the given value

Print the BST nodes in ascending order after deletion

💡 Why This Matters

🌍 Real World

BSTs are used in databases and file systems to keep data sorted and allow fast search, insert, and delete operations.

💼 Career

Understanding BST delete operations is important for software engineers working on data storage, search engines, and performance-critical applications.

1

Create the BST with given nodes

Create a class Node with int data, Node left, and Node right. Then create a BST by manually linking nodes with these exact values: root node with 50, left child 30, right child 70, left child of 30 is 20, right child of 30 is 40, left child of 70 is 60, right child of 70 is 80. Store the root node in a variable called root.

DSA C#

// Define Node class and create BST with root 50 and children as described
// Your code here

Hint

Define the Node class first, then create nodes and link them exactly as described.

2

Set the value to delete

Create an integer variable called key and set it to 50. This is the value you will delete from the BST.

DSA C#

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

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

Node root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);
root.left.left = new Node(20);
root.left.right = new Node(40);
root.right.left = new Node(60);
root.right.right = new Node(80);

// Set the key to delete
// Your code here

Hint

Just create an integer variable named key and assign 50 to it.

3

Implement the BST delete operation

Write a method called DeleteNode that takes a Node root and an int key. It should delete the node with value key from the BST and return the new root. Use the standard BST delete logic: if the node has two children, replace it with its inorder successor (smallest node in right subtree). Then update the tree links accordingly. Call DeleteNode with root and key, and update root with the returned value.

DSA C#

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

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

Node root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);
root.left.left = new Node(20);
root.left.right = new Node(40);
root.right.left = new Node(60);
root.right.right = new Node(80);

int key = 50;

// Implement DeleteNode method and update root
// Your code here

Hint

Follow the BST delete steps carefully: find node, handle 0,1,2 children cases, use inorder successor for two children.

4

Print the BST in order after deletion

Write a method called InOrder that takes a Node root and prints the node values in ascending order separated by spaces. Then call InOrder(root) to print the updated BST after deletion.

DSA C#

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

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

Node root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);
root.left.left = new Node(20);
root.left.right = new Node(40);
root.right.left = new Node(60);
root.right.right = new Node(80);

int key = 50;

Node MinValueNode(Node node)
{
    Node current = node;
    while (current.left != null)
    {
        current = current.left;
    }
    return current;
}

Node DeleteNode(Node rootNode, int keyToDelete)
{
    if (rootNode == null)
        return rootNode;

    if (keyToDelete  rootNode.data)
        rootNode.right = DeleteNode(rootNode.right, keyToDelete);
    else
    {
        if (rootNode.left == null)
            return rootNode.right;
        else if (rootNode.right == null)
            return rootNode.left;

        Node temp = MinValueNode(rootNode.right);
        rootNode.data = temp.data;
        rootNode.right = DeleteNode(rootNode.right, temp.data);
    }
    return rootNode;
}

root = DeleteNode(root, key);

// Implement InOrder method and print the BST
// Your code here

Hint

Use recursion to print left subtree, then current node, then right subtree. This prints nodes in ascending order.

Practice

1. What happens when you delete a leaf node (a node with no children) from a Binary Search Tree (BST)?

easy

A. The node is replaced by its right child.

B. The entire tree is restructured from the root.

C. The node is replaced by its left child.

D. The node is simply removed without affecting other nodes.

Solution

1. Step 1: Understand leaf node deletion

   A leaf node has no children, so removing it does not affect other nodes.

2. Step 2: Effect on BST structure

   Since no children exist, no restructuring is needed; just remove the node.

3. Final Answer:

   The node is simply removed without affecting other nodes. -> Option D

4. Quick Check:

   Leaf node deletion = simple removal [OK]

Hint: Leaf nodes delete by direct removal only [OK]

Common Mistakes:

• Thinking the tree restructures after leaf deletion
• Replacing leaf node with a child that doesn't exist
• Confusing leaf node deletion with internal node deletion

2. Which of the following is the correct C# syntax to delete a node with value 10 from a BST using a method named DeleteNode?

easy

A. root.DeleteNode(10);

B. root = DeleteNode(root, 10);

C. DeleteNode(root, 10);

D. DeleteNode(10, root);

Solution

1. Step 1: Understand method signature

   Usually, BST delete methods return the new root after deletion, so assignment is needed.

2. Step 2: Correct method call syntax

   Calling DeleteNode(root, 10) returns updated root, so root = DeleteNode(root, 10); is correct.

3. Final Answer:

   root = DeleteNode(root, 10); -> Option B

4. Quick Check:

   Assign returned root after deletion [OK]

Hint: Assign returned root after delete call [OK]

Common Mistakes:

• Not assigning the returned root after deletion
• Calling delete as instance method on root node
• Passing arguments in wrong order

3. Given the BST below and the C# code to delete node 15, what is the in-order traversal output after deletion?

      20
     /  \
   10    30
     
     15

root = DeleteNode(root, 15);

medium

A. [10, 20, 30]

B. [10, 15, 20, 30]

C. [20, 30]

D. [10, 20, 15, 30]

Solution

1. Step 1: Identify node to delete and its position

   Node 15 is a leaf node (no children) under 10.

2. Step 2: Delete node 15 and perform in-order traversal

   After deleting 15, in-order traversal visits nodes in ascending order: 10, 20, 30.

3. Final Answer:

   [10, 20, 30] -> Option A

4. Quick Check:

   In-order after deleting leaf = sorted without deleted node [OK]

Hint: In-order skips deleted leaf node [OK]

Common Mistakes:

• Including deleted node in traversal output
• Misordering nodes in traversal
• Confusing pre-order or post-order with in-order

4. Consider this C# method snippet for deleting a node from a BST:

Node DeleteNode(Node root, int key) {
  if (root == null) return root;
  if (key < root.val) root.left = DeleteNode(root.left, key);
  else if (key > root.val) root.right = DeleteNode(root.right, key);
  else {
    if (root.left == null) return root.right;
    else if (root.right == null) return root.left;
    root.val = MinValue(root.right);
    root.right = DeleteNode(root.right, root.val);
  }
  return root;
}

What is the bug in this code?

medium

A. The method does not update root.left or root.right after recursive calls.

B. The method does not handle the case when both children exist properly.

C. The method does not handle deleting leaf nodes correctly.

D. The method does not return the updated root after deletion.

Solution

1. Step 1: Analyze deletion when both children exist

   The method correctly replaces root's value with the minimum in the right subtree and deletes that minimum node recursively.

2. Step 2: Check correctness of recursive updates

   The method updates root.left and root.right after recursive calls, so this is handled properly.

3. Step 3: Identify the actual bug

   There is no bug in handling both children case or returning root; the code is correct.

4. Final Answer:

   None of the provided options correctly identify a bug. -> Option A

Hint: Check both children case carefully [OK]

Common Mistakes:

• Thinking leaf deletion is buggy here
• Missing recursive update of child pointers
• Assuming method forgets to return root

5. You have a BST with nodes: 50, 30, 70, 20, 40, 60, 80. You delete node 50 (the root). Which node replaces the root to maintain BST properties?

hard

A. Node 30 (left child of root)

B. Node 40 (maximum in left subtree)

C. Node 60 (minimum in right subtree)

D. Node 70 (right child of root)

Solution

1. Step 1: Identify node to delete and its children

   Node 50 is root with two children: left subtree (30, 20, 40) and right subtree (70, 60, 80).

2. Step 2: Find replacement node for root deletion

   Standard BST deletion replaces node with minimum node in right subtree, which is 60.

3. Final Answer:

   Node 60 (minimum in right subtree) -> Option C

4. Quick Check:

   Root replaced by min right subtree node [OK]

Hint: Replace deleted node with min right subtree node [OK]

Common Mistakes:

• Replacing with max left subtree instead of min right
• Replacing with immediate child without checking subtree
• Confusing replacement rules for BST deletion