BST Delete Operation in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after deleting a leaf node in BST

What is the printed state of the BST after deleting the leaf node with value 20?

DSA Go

package main
import "fmt"
type Node struct {
    val   int
    left  *Node
    right *Node
}
func insert(root *Node, val int) *Node {
    if root == nil {
        return &Node{val: val}
    }
    if val < root.val {
        root.left = insert(root.left, val)
    } else {
        root.right = insert(root.right, val)
    }
    return root
}
func inorder(root *Node) {
    if root != nil {
        inorder(root.left)
        fmt.Print(root.val, " -> ")
        inorder(root.right)
    }
}
func minValueNode(node *Node) *Node {
    current := node
    for current.left != nil {
        current = current.left
    }
    return current
}
func deleteNode(root *Node, key int) *Node {
    if root == nil {
        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 == nil {
            return root.right
        } else if root.right == nil {
            return root.left
        }
        temp := minValueNode(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)
    }
    return root
}
func main() {
    var root *Node
    vals := []int{50, 30, 20, 40, 70, 60, 80}
    for _, v := range vals {
        root = insert(root, v)
    }
    root = deleteNode(root, 20)
    inorder(root)
    fmt.Print("null\n")
}

A 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> null

B 30 -> 40 -> 50 -> 60 -> 70 -> null

C 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> null

D 50 -> 30 -> 40 -> 70 -> 60 -> 80 -> null

💡 Hint

Deleting a leaf node removes it without affecting other nodes.

Deleting 20 removes the leaf node 20. The inorder traversal prints nodes in sorted order without 20.

❓ Predict Output

intermediate

Output after deleting a node with one child in BST

What is the printed state of the BST after deleting the node with value 30, which has one child?

DSA Go

package main
import "fmt"
type Node struct {
    val   int
    left  *Node
    right *Node
}
func insert(root *Node, val int) *Node {
    if root == nil {
        return &Node{val: val}
    }
    if val < root.val {
        root.left = insert(root.left, val)
    } else {
        root.right = insert(root.right, val)
    }
    return root
}
func inorder(root *Node) {
    if root != nil {
        inorder(root.left)
        fmt.Print(root.val, " -> ")
        inorder(root.right)
    }
}
func minValueNode(node *Node) *Node {
    current := node
    for current.left != nil {
        current = current.left
    }
    return current
}
func deleteNode(root *Node, key int) *Node {
    if root == nil {
        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 == nil {
            return root.right
        } else if root.right == nil {
            return root.left
        }
        temp := minValueNode(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)
    }
    return root
}
func main() {
    var root *Node
    vals := []int{50, 30, 20, 40, 70, 60, 80}
    for _, v := range vals {
        root = insert(root, v)
    }
    root = deleteNode(root, 30)
    inorder(root)
    fmt.Print("null\n")
}

A 20 -> 40 -> 50 -> 60 -> 70 -> 80 -> null

B 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> null

C 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> null

D 40 -> 50 -> 60 -> 70 -> 80 -> null

💡 Hint

Deleting a node with one child replaces it with its child.

Node 30 has two children, but after deletion, its left child 20 and right child 40 remain. The node 30 is replaced by its right child 40, and 20 remains as left child of 40.

❓ Predict Output

advanced

Output after deleting a node with two children in BST

What is the printed state of the BST after deleting the node with value 50, which has two children?

DSA Go

package main
import "fmt"
type Node struct {
    val   int
    left  *Node
    right *Node
}
func insert(root *Node, val int) *Node {
    if root == nil {
        return &Node{val: val}
    }
    if val < root.val {
        root.left = insert(root.left, val)
    } else {
        root.right = insert(root.right, val)
    }
    return root
}
func inorder(root *Node) {
    if root != nil {
        inorder(root.left)
        fmt.Print(root.val, " -> ")
        inorder(root.right)
    }
}
func minValueNode(node *Node) *Node {
    current := node
    for current.left != nil {
        current = current.left
    }
    return current
}
func deleteNode(root *Node, key int) *Node {
    if root == nil {
        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 == nil {
            return root.right
        } else if root.right == nil {
            return root.left
        }
        temp := minValueNode(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)
    }
    return root
}
func main() {
    var root *Node
    vals := []int{50, 30, 20, 40, 70, 60, 80}
    for _, v := range vals {
        root = insert(root, v)
    }
    root = deleteNode(root, 50)
    inorder(root)
    fmt.Print("null\n")
}

A 30 -> 40 -> 60 -> 70 -> 80 -> null

B 20 -> 30 -> 40 -> 60 -> 70 -> 80 -> null

C 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> null

D 20 -> 30 -> 40 -> 60 -> 70 -> 80 -> 50 -> null

💡 Hint

Deleting a node with two children replaces it with the smallest node in the right subtree.

Node 50 is replaced by 60 (smallest in right subtree). Then 60 is deleted from its original position.

🔧 Debug

advanced

Identify the error in BST delete function

What error will occur when running this BST delete function if the node to delete has no children?

DSA Go

func deleteNode(root *Node, key int) *Node {
    if root == nil {
        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 == nil {
            return root.right
        } else if root.right == nil {
            return root.left
        }
        temp := minValueNode(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)
    }
    return root
}

// Assume minValueNode is correctly implemented.

A No error, function works correctly for leaf nodes

B Nil pointer dereference when deleting leaf node

C Stack overflow due to infinite recursion

D Compilation error due to missing return statement

💡 Hint

Check how leaf nodes are handled in the code.

The function correctly returns nil when deleting a leaf node (both children nil). No error occurs.

🧠 Conceptual

expert

Minimum number of nodes in BST after deleting root with two children

Given a BST with 7 nodes inserted in this order: 50, 30, 20, 40, 70, 60, 80. After deleting the root node (50), what is the minimum number of nodes remaining in the BST?

A 4

B 5

C 7

D 6

💡 Hint

Deleting a node removes exactly one node from the tree.

Deleting the root node removes one node. The BST had 7 nodes, so 6 remain.

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's children replace it in the tree.

B. The entire tree is rebuilt from scratch.

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

D. The root node is always changed.

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, simply remove the node and update its parent's pointer to null.

3. Final Answer:

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

4. Quick Check:

   Leaf node deletion = simple removal [OK]

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

Common Mistakes:

• Thinking children need rearrangement
• Assuming root always changes
• Believing tree rebuild is needed

2. Which of the following Go function signatures correctly represents a BST delete operation for a node with integer keys?

easy

A. func deleteNode(key int, root *Node) *Node

B. func deleteNode(root *Node, key int) *Node

C. func deleteNode(root Node, key int) Node

D. func deleteNode(root *Node, key string) *Node

Solution

1. Step 1: Check parameter order and types

   The root node pointer should be first, key integer second, returning updated root pointer.

2. Step 2: Validate pointer usage and key type

   Root must be a pointer to allow tree modification; key must be int for integer keys.

3. Final Answer:

   func deleteNode(root *Node, key int) *Node -> Option B

4. Quick Check:

   Correct signature = root pointer first, int key [OK]

Hint: Root pointer first, int key second, returns updated root [OK]

Common Mistakes:

• Swapping parameter order
• Using value instead of pointer for root
• Using wrong key type

3. Given the BST below and the Go code to delete node with key 10, what is the in-order traversal output after deletion? BST structure: 15 / \ 10 20 / \ 8 12 Go code snippet:

root = deleteNode(root, 10)

medium

A. [12, 15, 20]

B. [8, 15, 20]

C. [8, 10, 12, 15, 20]

D. [8, 12, 15, 20]

Solution

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

   Node 10 has two children: 8 (left) and 12 (right).

2. Step 2: Replace node 10 with its in-order successor

   In-order successor is 12. Replace 10 with 12, then delete original 12 node.

3. Step 3: Perform in-order traversal after deletion

   Traversal order: 8, 12, 15, 20.

4. Final Answer:

   [8, 12, 15, 20] -> Option D

5. Quick Check:

   In-order after deleting 10 = [8, 12, 15, 20] [OK]

Hint: Replace deleted node with in-order successor [OK]

Common Mistakes:

• Deleting successor node incorrectly
• Skipping replacement step
• Confusing in-order predecessor with successor

4. Consider this Go code snippet for deleting a node from a BST. What is the bug?

func deleteNode(root *Node, key int) *Node {
    if root == nil {
        return nil
    }
    if key < root.key {
        root.left = deleteNode(root.left, key)
    } else if key > root.key {
        root.right = deleteNode(root.right, key)
    } else {
        if root.left == nil {
            return root.right
        } else if root.right == nil {
            return root.left
        }
        temp := findMin(root.right)
        root.key = temp.key
        deleteNode(root.right, temp.key)
    }
    return root
}

medium

A. Missing assignment of root.right after deleting successor node.

B. Incorrect base case for empty tree.

C. Wrong comparison operators for key checks.

D. Returning nil instead of root in all cases.

Solution

1. Step 1: Analyze deletion of node with two children

   After replacing root.key with successor's key, the successor node must be deleted from right subtree.

2. Step 2: Check recursive call effect on tree structure

   The call deleteNode(root.right, temp.key) is made but its result is not assigned back to root.right, so the successor node remains.

3. Final Answer:

   Missing assignment of root.right after deleting successor node. -> Option A

4. Quick Check:

   Assign recursive delete result to root.right [OK]

Hint: Always assign recursive delete results to child pointers [OK]

Common Mistakes:

• Ignoring returned subtree after deletion
• Not updating pointers after recursive calls
• Confusing base case with recursive case

5. You have a BST with nodes: 30, 20, 40, 10, 25, 35, 50. You delete node 30 (root). Which node becomes the new root after deletion using the standard BST delete operation?

hard

A. Node 35 (in-order successor)

B. Node 25 (in-order predecessor)

C. Node 40 (right child)

D. Node 20 (left child)

Solution

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

   Node 30 is root with two children: left subtree (20) and right subtree (40).

2. Step 2: Find in-order successor of node 30

   In-order successor is the smallest node in right subtree, which is 35.

3. Step 3: Replace root with in-order successor

   Replace 30 with 35, then delete original 35 node from right subtree.

4. Final Answer:

   Node 35 (in-order successor) -> Option A

5. Quick Check:

   Root replaced by in-order successor = 35 [OK]

Hint: Root replaced by smallest node in right subtree [OK]

Common Mistakes:

• Using in-order predecessor instead of successor
• Choosing direct child without successor check
• Not deleting successor node after replacement