BST Delete Operation in DSA Go

Mental Model

Deleting a node in a BST means removing it while keeping the tree's order intact. We find the node, then rearrange its children carefully.

Analogy: Imagine removing a book from a sorted bookshelf. If the book has no neighbors, just take it out. If it has one neighbor, slide that neighbor in. If it has two neighbors, replace it with the next book in order and then remove that next book.

      5
     / \
    3   7
   / \   \
  2   4   8

Dry Run Walkthrough

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

Goal: Remove node 3 and keep BST order correct

Step 1: Find node with value 3 starting from root

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

Why: We must 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 3

Step 4: Delete the original node 4 (now duplicate) which has no children

      5
     / \ 
    4   7
   /     \
  2       8

Why: Remove duplicate node to complete deletion

Result:

      5
     / \ 
    4   7
   /     \
  2       8

Annotated Code

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 findMin(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 nil
    }
    if key < root.val {
        root.left = deleteNode(root.left, key) // traverse left subtree
    } else if key > root.val {
        root.right = deleteNode(root.right, key) // traverse right subtree
    } else {
        // found node to delete
        if root.left == nil {
            return root.right // replace node with right child
        } else if root.right == nil {
            return root.left // replace node with left child
        }
        // node with two children
        minRight := findMin(root.right) // find inorder successor
        root.val = minRight.val         // copy successor's value
        root.right = deleteNode(root.right, minRight.val) // delete successor
    }
    return root
}

func printInOrder(root *Node) {
    if root == nil {
        return
    }
    printInOrder(root.left)
    fmt.Printf("%d -> ", root.val)
    printInOrder(root.right)
}

func main() {
    var root *Node
    values := []int{5, 3, 7, 2, 4, 8}
    for _, v := range values {
        root = insert(root, v)
    }
    root = deleteNode(root, 3)
    printInOrder(root)
    fmt.Print("null\n")
}

if key < root.val { root.left = deleteNode(root.left, key) // traverse left subtree } else if key > root.val { root.right = deleteNode(root.right, key) // traverse right subtree } else {

search for node to delete by comparing key with current node value

if root.left == nil { return root.right // replace node with right child } else if root.right == nil { return root.left // replace node with left child }

handle cases where node has zero or one child by replacing it with child or nil

minRight := findMin(root.right) // find inorder successor root.val = minRight.val // copy successor's value root.right = deleteNode(root.right, minRight.val) // delete successor

for two children, replace node value with inorder successor and delete successor

Output

2 -> 4 -> 5 -> 7 -> 8 -> null

Complexity Analysis

Time: O(h) because we traverse from root to the node to delete, where h is tree height

Space: O(h) due to recursion stack in worst case of unbalanced 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 Go

if root == nil {
        return nil
    }

Deleting a leaf node (no children)

Node is simply removed by returning nil to parent

DSA Go

if root.left == nil {
            return root.right
        } else if root.right == nil {
            return root.left
        }

Deleting root node with two children

Root value replaced with inorder successor and successor node deleted

DSA Go

minRight := findMin(root.right)

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 finding the minimum node in right subtree and replace value before deleting successor

Mistake: Deleting node without reconnecting children properly
Fix: Return the correct child node to parent after deletion to maintain tree structure

Summary

Deletes a node from a BST while maintaining its sorted order.

Use when you want to remove a value from a BST without breaking its properties.

The key is to replace a node with two children by its inorder successor to keep order.