We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Delete Node in a BST

Difficulty: Medium

Problem Description

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. The deletion can be divided into two stages: Search for a node to remove, and if the node is found, delete the node.

Key Insights

  • A Binary Search Tree (BST) maintains the property that for any given node, all values in its left subtree are less than its value, and all values in its right subtree are greater.
  • Deleting a node can have three cases:
    1. The node is a leaf (no children).
    2. The node has one child.
    3. The node has two children (in which case we need to find the in-order predecessor or successor to replace the node).
  • The deletion operation must maintain the BST properties.

Space and Time Complexity

Time Complexity: O(height of tree), where height is the depth of the tree.
Space Complexity: O(height of tree) due to the recursion stack.

Solution

To solve this problem, we will use a recursive approach. We will traverse the tree to find the node with the given key. Once found, we will handle the three cases of deletion:

  1. If the node is a leaf, simply remove it.
  2. If the node has one child, replace it with its child.
  3. If the node has two children, find the in-order predecessor (maximum node in the left subtree) or in-order successor (minimum node in the right subtree), replace the node's value with that of the predecessor/successor, and then delete the predecessor/successor.

We will return the updated root of the BST after deletion.

Code Solutions

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

def deleteNode(root: TreeNode, key: int) -> TreeNode:
    if not root:
        return None
    if key < root.val:
        root.left = deleteNode(root.left, key)  # Search in the left subtree
    elif key > root.val:
        root.right = deleteNode(root.right, key)  # Search in the right subtree
    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 (smallest in the right subtree)
        min_larger_node = root.right
        while min_larger_node.left:
            min_larger_node = min_larger_node.left
        root.val = min_larger_node.val  # Replace value with successor's value
        root.right = deleteNode(root.right, min_larger_node.val)  # Delete the successor
    return root
← Back to All Questions