BST Delete Operation in DSA C#

Mental Model

To remove a value from a BST, find the node and adjust the tree so it still keeps order.

Analogy: Imagine removing a book from a sorted shelf. If the book is alone, just take it out. If it has neighbors, you might need to shift or replace it with a similar book to keep the order.

    5
   / \
  3   7
 / \   \
2   4   8
↑root

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, delete value 3

Goal: Remove node with value 3 and keep BST order intact

Step 1: Find node with value 3 starting from root

    5
   / \
  3↑  7
 / \   \
2   4   8

Why: We need to locate the node to delete

Step 2: Node 3 has two children, find its inorder successor (smallest in right subtree), which is 4

    5
   / \
  3↑  7
 / \   \
2   4↑  8

Why: Replacing node 3 with 4 keeps BST order

Step 3: Replace node 3's value with 4

    5
   / \
  4↑  7
 / \   \
2   4   8

Why: We copy successor's value to node to delete

Step 4: Delete original node with value 4 (successor), which has no left child

    5
   / \
  4↑  7
 /     \
2       8

Why: Remove duplicate successor node safely

Result:

    5
   / \
  4   7
 /     \
2       8

Annotated Code

DSA C#

using System;

class Node
{
    public int val;
    public Node left, right;
    public Node(int v) { val = v; left = right = null; }
}

class BST
{
    public Node root;

    public Node Delete(Node root, int key)
    {
        if (root == null) return null; // base case: empty subtree

        if (key < root.val)
            root.left = Delete(root.left, key); // go left
        else if (key > root.val)
            root.right = Delete(root.right, key); // go right
        else
        {
            // found node to delete
            if (root.left == null) return root.right; // no left child
            else if (root.right == null) return root.left; // no right child

            // node with two children: get inorder successor
            Node succ = MinValueNode(root.right);
            root.val = succ.val; // copy successor value
            root.right = Delete(root.right, succ.val); // delete successor
        }
        return root;
    }

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

    public void Insert(int val)
    {
        root = InsertRec(root, val);
    }

    private Node InsertRec(Node root, int val)
    {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = InsertRec(root.left, val);
        else root.right = InsertRec(root.right, val);
        return root;
    }

    public void PrintInOrder(Node node)
    {
        if (node == null) return;
        PrintInOrder(node.left);
        Console.Write(node.val + " ");
        PrintInOrder(node.right);
    }
}

class Program
{
    static void Main()
    {
        BST tree = new BST();
        int[] values = {5, 3, 7, 2, 4, 8};
        foreach (int v in values) tree.Insert(v);

        tree.root = tree.Delete(tree.root, 3);

        tree.PrintInOrder(tree.root);
        Console.WriteLine();
    }
}

if (root == null) return null; // base case: empty subtree

stop recursion when subtree is empty

if (key < root.val) root.left = Delete(root.left, key); // go left else if (key > root.val) root.right = Delete(root.right, key); // go right

search for node to delete by comparing key

if (root.left == null) return root.right; // no left child else if (root.right == null) return root.left; // no right child

handle nodes with zero or one child by bypassing node

Node succ = MinValueNode(root.right); root.val = succ.val; // copy successor value root.right = Delete(root.right, succ.val); // delete successor

replace node with inorder successor and delete successor

while (current.left != null) current = current.left; // find leftmost

find smallest node in right subtree

Output

2 4 5 7 8 

Complexity Analysis

Time: O(h) where h is tree height because we traverse from root to node to delete and possibly to successor

Space: O(h) due to recursion stack in worst case of skewed tree

vs Alternative: Compared to naive array deletion which requires shifting elements O(n), BST delete is faster for balanced trees with O(log n) height

Edge Cases

Deleting a node not present in the tree

Function returns original tree unchanged

DSA C#

if (root == null) return null; // base case: empty subtree

Deleting a leaf node (no children)

Node is simply removed by returning null to parent

DSA C#

if (root.left == null) return root.right; // no left child

Deleting root node with two children

Root value replaced by inorder successor and successor node deleted

DSA C#

Node succ = MinValueNode(root.right); root.val = succ.val; root.right = Delete(root.right, succ.val);

When to Use This Pattern

When you need to remove a value from a BST and keep it sorted, use the BST delete pattern that handles zero, one, or two children cases carefully.

Common Mistakes

Mistake: Not handling the two children case by replacing with inorder successor
Fix: Implement logic to find successor, copy its value, then delete successor node

Mistake: Forgetting to update parent's child pointer after deletion
Fix: Always assign returned subtree root back to parent's left or right pointer

Summary

Deletes a node from BST while maintaining BST properties.

Use when you need to remove a value from a BST without breaking order.

The key is replacing a node with two children by its inorder successor to keep the tree sorted.

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