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

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))