Delete a Node in a Binary Search Tree

Algorithm Steps

Given a binary search tree (BST) and a key to delete.
If the BST is empty, return null or the empty tree.
If key is less than the value at the current node, recursively delete the node in the left subtree.
If key is greater than the value at the current node, recursively delete the node in the right subtree.
If key equals the current node's value, then this is the node to be deleted:

If the node is a leaf, remove it.
If the node has one child, replace it with its child.
If the node has two children, find the minimum node in its right subtree (successor), copy its value to the current node, and then recursively delete the successor from the right subtree.

Return the (possibly new) root of the BST.

Delete a Node in a Binary Search Tree - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findMin(node):
    while node.left:
        node = node.left
    return node


def deleteNode(root, key):
    if not root:
        return root
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        # Node with only one child or no child
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        # Node with two children: Get the inorder successor
        temp = findMin(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)
    return root

# Example usage:
if __name__ == '__main__':
    # Build a BST and delete a node with key
    root = TreeNode(5,
            TreeNode(3, TreeNode(2), TreeNode(4)),
            TreeNode(7, TreeNode(6), TreeNode(8)))
    root = deleteNode(root, 3)
    # Function to print inorder traversal for verification
    def inorder(root):
        return inorder(root.left) + [root.val] + inorder(root.right) if root else []
    print('Inorder after deletion:', inorder(root))