Introduction

In this blog post, we will explore how to solve the LeetCode problem "450" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. Basically, the deletion can be divided into two stages: Search for a node to remove. If the node is found, delete the node. Example 1: Input: root = [5,3,6,2,4,null,7], key = 3 Output: [5,4,6,2,null,null,7] Explanation: Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the above BST. Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted. Example 2: Input: root = [5,3,6,2,4,null,7], key = 0 Output: [5,3,6,2,4,null,7] Explanation: The tree does not contain a node with value = 0. Example 3: Input: root = [], key = 0 Output: [] Constraints: The number of nodes in the tree is in the range [0, 104]. -105 <= Node.val <= 105 Each node has a unique value. root is a valid binary search tree. -105 <= key <= 105 Follow up: Could you solve it with time complexity O(height of tree)?

Explanation

Here's the breakdown of the approach, complexity, and the Python code for deleting a node in a BST:

• High-Level Approach:

  • Search: Recursively traverse the BST to find the node to delete. Use BST properties (left subtree < node < right subtree) for efficient searching.
  • Deletion: If the node is found:
    • If it's a leaf node, simply remove it.
    • If it has one child, replace the node with its child.
    • If it has two children, replace the node with its inorder successor (minimum node in the right subtree) and then delete the inorder successor from the right subtree.
  • Update Root: Return the (potentially updated) root node after deletion.

• Complexity:

  • Runtime Complexity: O(height of tree) - in the worst case (skewed tree), it degrades to O(n), where n is the number of nodes. In the best case (balanced tree), it is O(log n).
  • Storage Complexity: O(height of tree) - due to the recursive call stack. Similar to runtime, this can be O(n) for skewed trees and O(log n) for balanced trees.

Code

    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)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        # Node to be deleted found

        # Case 1: Node has no child or only one child
        if not root.left:
            return root.right
        elif not root.right:
            return root.left

        # Case 2: Node has two children
        # Find inorder successor (smallest in the right subtree)
        min_node = root.right
        while min_node.left:
            min_node = min_node.left

        # Copy the inorder successor's value to this node
        root.val = min_node.val

        # Delete the inorder successor from the right subtree
        root.right = deleteNode(root.right, min_node.val)

    return root