BSTDELETE - Editorial

editorial
1

Prerequisites :- Binary Search Trees, BT traversals.

Problem :- Given a Binary Search Tree (BST) and a target node X, delete the node from the BST. The goal is to return the reference to the root node, which may be modified after the deletion process.

Solution Approach :-

The provided solution implements the deletion of a node in a BST through a recursive approach. The process involves searching for the target node and then performing the deletion based on different cases.

Algorithm:

    1. If the root is null, return null (base case).
    1. If the target value x is less than the root’s value, recursively call deleteNode on the left subtree.
    1. If x is greater than the root’s value, recursively call deleteNode on the right subtree.
    1. If x is equal to the root’s value:
    • If the node has no children (both left and right are null), return null.
    • If the node has only one child, return that child.
    • If the node has two children, find the inorder successor (the smallest node in the right subtree), replace the root’s value with the successor’s value, and recursively call deleteNode on the right subtree to delete the successor.
    1. Return the modified root.

Time Complexity: The time complexity of this algorithm is O(h), where h is the height of the BST. In the worst case, for an unbalanced tree, the height can be equal to the number of nodes, resulting in O(n) time complexity.

Space Complexity: The space complexity is O(h) due to the recursive call stack. In the worst case, for an unbalanced tree, the height can be equal to the number of nodes, resulting in O(n) space complexity.

2

There seems to be a spelling error in the test case which causes it to fail while trying to submit with Java

Incorrect:
Succesfully deleted the node!

Correct:
Successfully deleted the node!

Kindly fix it. Thank you.

3

fixed. thanks again for reporting.

1 Like