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.