How do I delete a node from a binary search tree in Python?

How do I delete a node from a binary search tree in Python?

To delete a node from a binary search tree (BST) in Python, you need to consider three cases: deleting a leaf node, deleting a node with one child, and deleting a node with two children.

Can you show me the code for deleting a node with two children?

Sure! When deleting a node with two children, you typically replace it with its in-order successor. Here's a sample code:

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def delete_node(root, key):
    if root is None:
        return root
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        temp = min_value_node(root.right)
        root.val = temp.val
        root.right = delete_node(root.right, temp.val)
    return root

# Helper function to find the minimum value node
def min_value_node(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

What if I want to delete a node that doesn't exist?

If you try to delete a node that doesn't exist in the BST, the function will simply return the original tree without any modifications. You can check if the node exists by looking for it before attempting to delete.