Delete Node In A Bst

To solve this coding challenge, we need to perform the deletion of a given node in a Binary Search Tree (BST). Here's a detailed explanation of the steps involved followed by the pseudocode.

Explanation

Task Breakdown

  1. Search for the Node :
    • Traverse the BST to locate the node with the value
      key
      .
    • If the
      key
      is less than the node's value, move to the left subtree.
    • If the
      key
      is more than the node's value, move to the right subtree.
  2. Delete the Node :
    • Once the node is found, there are three possible scenarios for deletion:
      • Node with No Children : Simply remove the node.
      • Node with One Child : Replace the node with its child.
      • Node with Two Children : Find the node’s in-order successor (smallest node in the right subtree), replace the node’s value with the successor's value, then delete the successor.

    Constraints

  3. The number of nodes in the tree ranges from 0 to 10^4.
  4. Each node has a unique value.
  5. root
    is a valid binary search tree.
  6. The value of the key is within the range: -10^5 <= key <= 10^5.
  7. Detailed Steps in Pseudocode

  8. Initialize Function to Delete Node :
    • Accept the root node and the key to delete.
  9. Base Case :
    • If the root is null, return null (indicating that the node was not found).
  10. Traverse BST :
    • If the key is smaller than the current node’s value, attempt to delete the key from the left subtree.
    • If the key is larger, attempt to delete the key from the right subtree.
    • If the current node’s value matches the key, process deletion.
  11. Node Deletion Scenarios :
    • Leaf Node : Simply return null to remove the node.
    • Single Child Node : Return the single child (left or right) to remove the node.
    • Two Children Node : Find the in-order successor, replace the current node’s value with the successor's value, and then recursively delete the successor.
  12. Return Updated Root :
    • Continue returning the root after each deletion step.

Pseudocode with Comments

                                            
# Function to delete a node in the BST
function deleteNode(root, key):
    # Base case: when root is null
    if root is null:
        return null
    
    # If the key to be deleted is smaller than the root's value,
    # then it lies in the left subtree
    if key < root.value:
        root.left = deleteNode(root.left, key)
    
    # If the key to be deleted is greater than the root's value,
    # then it lies in the right subtree
    elif key > root.value:
        root.right = deleteNode(root.right, key)
    
    # If the key is the same as the root's value,
    # this is the node to be deleted
    else:
        # Node with only one child or no child
        if root.left is null:
            return root.right
        elif root.right is null:
            return root.left
        
        # Node with two children:
        # Get the in-order successor (smallest in the right subtree)
        successor = root.right
        while successor.left is not null:
            successor = successor.left
        
        # Copy the in-order successor's content to this node
        root.value = successor.value
        
        # Delete the in-order successor
        root.right = deleteNode(root.right, successor.value)
    
    return root

                                        
This pseudocode outlines the process of finding and deleting a node in a BST. All scenarios are covered: when a node has no children, one child, or two children. The in-order successor is used to replace the value of a node that has two children to maintain the BST properties.