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
- Search for the Node :
-
Traverse the BST to locate the node with the value
key
-
If the
key
-
If the
key
- 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.
- The number of nodes in the tree ranges from 0 to 10^4.
- Each node has a unique value.
-
root
- The value of the key is within the range: -10^5 <= key <= 10^5.
- Initialize Function to Delete Node :
- Accept the root node and the key to delete.
- Base Case :
- If the root is null, return null (indicating that the node was not found).
- 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.
- 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.
- Return Updated Root :
- Continue returning the root after each deletion step.
Constraints
Detailed Steps in Pseudocode
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.