BST Delete Operation in DSA Go - 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 structure valid.

🎯 Goal: Build a Go program that creates a BST, sets a value to delete, performs the delete operation correctly, and prints the BST in-order after deletion.

📋 What You'll Learn

Create a BST with these exact values inserted in order: 50, 30, 70, 20, 40, 60, 80

Create a variable called keyToDelete and set it to 50

Implement a function called deleteNode that deletes a node with the given key from the BST

Print the BST nodes in ascending order after deletion using in-order traversal

💡 Why This Matters

🌍 Real World

BSTs are used in databases and file systems to keep data sorted and allow fast insertions, deletions, and lookups.

💼 Career

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

1

Create BST with given values

Create a struct called Node with Val int, Left *Node, and Right *Node. Then create a function called insert that inserts a value into the BST. Finally, create a BST by inserting these values in order: 50, 30, 70, 20, 40, 60, 80. Store the root in a variable called root.

DSA Go

// Define Node struct
// Define insert function
// Insert values 50, 30, 70, 20, 40, 60, 80 into BST and assign to root
// Your code here

Hint

Define the Node struct with integer value and pointers to left and right children. Use recursion in insert to place values correctly.

2

Set the key to delete

Create a variable called keyToDelete and set it to 50.

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.Right = insert(root.Right, val)
    }
    return root
}

func main() {
    var root *Node
    root = insert(root, 50)
    root = insert(root, 30)
    root = insert(root, 70)
    root = insert(root, 20)
    root = insert(root, 40)
    root = insert(root, 60)
    root = insert(root, 80)

    // Create keyToDelete variable and set to 50
    // Your code here
}

Hint

Use keyToDelete := 50 to create and set the variable.

3

Implement deleteNode function

Implement a function called deleteNode that takes root *Node and key int and returns *Node. It should delete the node with value key from the BST and return the new root. Use the standard BST delete logic: if node has two children, replace with inorder successor.

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.Right = insert(root.Right, val)
    }
    return root
}

// Implement deleteNode function here
// Your code here

func main() {
    var root *Node
    root = insert(root, 50)
    root = insert(root, 30)
    root = insert(root, 70)
    root = insert(root, 20)
    root = insert(root, 40)
    root = insert(root, 60)
    root = insert(root, 80)

    keyToDelete := 50
}

Hint

Use recursion to find the node. Handle three cases: no child, one child, two children. For two children, find the smallest node in right subtree (inorder successor) and replace.

4

Delete node and print in-order traversal

Call deleteNode with root and keyToDelete and assign the result back to root. Then implement a function called inOrder that prints the BST nodes in ascending order separated by spaces. Finally, call inOrder(root) to print the BST after deletion.

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.Right = insert(root.Right, val)
    }
    return root
}

func minValueNode(node *Node) *Node {
    current := node
    for current != nil && 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.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
}

// Implement inOrder function to print BST nodes in ascending order
// Call deleteNode and print the BST
// Your code here

Hint

Call deleteNode with root and keyToDelete. Then print the BST using in-order traversal to show sorted values.