Delete a Node in Binary Search Tree in Kotlin | BST

by

To delete a node in a binary search tree, we need to perform the following steps:

  1. Find the node to be deleted.
  2. If the node has no child, simply delete it.
  3. If the node has only one child, replace the node with its child.
  4. If the node has two children, find its in-order successor (i.e., the smallest node in its right subtree), copy the in-order successor’s value to the node to be deleted, and then delete the in-order successor.
Kotlin
class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}
fun deleteNode(root: TreeNode?, key: Int): TreeNode? {
    if (root == null) {
        return null
    }   
    if (key < root.`val`) {
        root.left = deleteNode(root.left, key)
    } else if (key > root.`val`) {
        root.right = deleteNode(root.right, key)
    } else {
        // Case 1: No child
        if (root.left == null && root.right == null) {
            return null
        }
        // Case 2: One child
        else if (root.left == null) {
            return root.right
        } else if (root.right == null) {
            return root.left
        }
        // Case 3: Two children
        else {
            val successor = findSuccessor(root.right!!)
            root.`val` = successor.`val`
            root.right = deleteNode(root.right, successor.`val`)
        }
    }
    return root
}
fun findSuccessor(node: TreeNode): TreeNode {
    var curr = node
    while (curr.left != null) {
        curr = curr.left!!
    }
    return curr
}
fun main() {
    val root = TreeNode(5)
    root.left = TreeNode(3)
    root.right = TreeNode(7)
    root.left?.left = TreeNode(2)
    root.left?.right = TreeNode(4)
    root.right?.left = TreeNode(6)
    root.right?.right = TreeNode(8)

    println("Binary Search Tree before deletion:")
    printTree(root)
    println()

    val key = 5
    val updatedRoot = deleteNode(root, key)

    println("Binary Search Tree after deletion of node with key $key:")
    printTree(updatedRoot)
}
fun printTree(root: TreeNode?) {
    if (root == null) {
        return
    }
    printTree(root.left)
    print("${root.`val`} ")
    printTree(root.right)
}

The deleteNode function takes the root of the binary search tree and the key of the node to be deleted as input, and returns the updated root of the binary search tree after the deletion operation. The findSuccessor function finds the in-order successor of a given node in the binary search tree.

In the deleteNode function, we first check if the root is null. If so, we return null because the node to be deleted cannot be found in an empty tree. Then, we recursively search for the node to be deleted by comparing its key with the keys of the nodes in the left and right subtrees. Once we find the node to be deleted, we check its number of children using the three cases described above. Finally, we update the binary search tree accordingly and return the updated root.

main function that demonstrates the usage of the deleteNode function to delete a node from a binary search tree:

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

This code first creates a binary search tree with root value 5 and six other nodes, and then prints the tree using an in-order traversal. After that, it calls the deleteNode function to delete the node with key 5 from the tree, and prints the updated tree again using an in-order traversal. The output of this code should look like this:

Binary Search Tree before deletion:
2 3 4 5 6 7 8
Binary Search Tree after deletion of node with key 5:
2 3 4 6 7 8

Leave a Comment