## Similar Problems

Similar Problems not available

# Delete Node In A Bst - Leetcode Solution

LeetCode: Delete Node In A Bst Leetcode Solution

Difficulty: Medium

Topics: binary-search-tree tree binary-tree

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 function should first find the node to delete, and then delete it accordingly while preserving the properties of the BST.

Solution:

Approach:

The first step in solving the problem is to find the node to delete. After that, there are three cases to consider:

Case 1: If the node to delete is a leaf node (node with no children), simply delete it from the tree.

Case 2: If the node to delete has only one child, replace the node with its child.

Case 3: If the node to delete has two children, replace the node with its inorder successor or predecessor. The inorder predecessor is the largest node in the left subtree, while the inorder successor is the smallest node in the right subtree.

Algorithm:

- If the root is None, return None.
- If the root's value matches the key, then we need to delete this node.
- If the key is less than the root's value, then the node to delete must be in the left subtree. Recursively call the delete function on the left subtree and update the left child of the root accordingly.
- If the key is greater than the root's value, then the node to delete must be in the right subtree. Recursively call the delete function on the right subtree and update the right child of the root accordingly.
- If the node to delete has both left and right children, then find its inorder successor or predecessor. If the inorder predecessor is found, then set the root value to the predecessor's value and recursively delete the predecessor in the left subtree. Similarly, if the inorder successor is found, then set the root value to the successor's value and recursively delete the successor in the right subtree.
- If the node to delete has only one child, then replace the node with its child.
- If the node to delete is a leaf node, simply delete it from the tree.

Implementation:

Here is the Python implementation of the above algorithm:

```
def deleteNode(root, key):
if root is None:
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 delete found
# Case 1: leaf node
if root.left is None and root.right is None:
return None
# Case 2: node has only one child
if root.left is None:
return root.right
elif root.right is None:
return root.left
# Case 3: node has two children
temp = root.right
while temp.left:
temp = temp.left
root.val = temp.val
root.right = deleteNode(root.right, temp.val)
return root
```

The time complexity of this algorithm is O(h), where h is the height of the BST. The worst-case time complexity of this algorithm is O(n) when the tree becomes a skewed tree.

## Delete Node In A Bst Solution Code

`1`