# Delete Node From Binary Search Tree

show

Problem Statement

Given a binary search tree and a key value. The task is to delete the given key from the BST and return the updated root node.

Examples:
Input:

Key = 3
Output: Shown in image

## Approach: Recursion

If you observe clearly, there are mainly three possible conditions.

• If the key to be deleted is a leaf node:
• In this case, simply make the node NULL.
• If the key to be deleted is not a leaf and has the right child.
• In this case, replace the node with its successor node.
• If the key to be deleted is not a leaf and has a left child and no right child.
• In this case, replace the node with its predecessor node.

Algorithm

• Compare the value of key with the value of root. If the key > root -> value, recursively traverse the right subtree.
• If key < root -> value, recursively traverse the left subtree.
• While traversing if key == root->value, we need to delete this node:
• If the node is a leaf, make root = NULL.
• If the node is not a leaf and has the right child, recursively replace its value with the successor node and delete its successor from its original position.
• If the node is not a leaf and has left child, but not right child, recursively replace its value by predecessor node and delete its predecessor from its original position.
• Return root

### C++ Code

```int successor(TreeNode * root) {
root = root -> right;
while (root -> left != NULL) root = root -> left;
return root -> val;
}
int predecessor(TreeNode * root) {
root = root -> left;
while (root -> right != NULL) root = root -> right;
return root -> val;
}

TreeNode * deleteNode(TreeNode * root, int key) {
if (root == NULL) return NULL;
if (key > root -> val) root -> right = deleteNode(root -> right, key);
else if (key < root -> val) root.left = deleteNode(root -> left, key);
else {
if (root -> left == NULL && root -> right == NULL) root = NULL;
else if (root -> right != NULL) {
root -> val = successor(root);
root.right = deleteNode(root -> right, root -> val);
} else {
root -> val = predecessor(root);
root -> left = deleteNode(root -> left, root -> val);
}
}
return root;
}```

### Java Code

```int successor(TreeNode * root) {
root = root -> right;
while (root -> left != NULL) root = root -> left;
return root -> val;
}
int predecessor(TreeNode * root) {
root = root -> left;
while (root -> right != NULL) root = root -> right;
return root -> val;
}

TreeNode * deleteNode(TreeNode * root, int key) {
if (root == NULL) return NULL;
if (key > root -> val) root -> right = deleteNode(root -> right, key);
else if (key < root -> val) root.left = deleteNode(root -> left, key);
else {
if (root -> left == NULL && root -> right == NULL) root = NULL;
else if (root -> right != NULL) {
root -> val = successor(root);
root.right = deleteNode(root -> right, root -> val);
} else {
root -> val = predecessor(root);
root -> left = deleteNode(root -> left, root -> val);
}
}
return root;
}
}```

### Python Code

```class Solution:
def successor(self, root):
root = root.right
while root.left:
root = root.left
return root.val

def predecessor(self, root):
root = root.left
while root.right:
root = root.right
return root.val

def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
if not root:
return None

if key > root.val:
root.right = self.deleteNode(root.right, key)
elif key < root.val:
root.left = self.deleteNode(root.left, key)
else:
if not (root.left or root.right):
root = None
elif root.right:
root.val = self.successor(root)
root.right = self.deleteNode(root.right, root.val)
else:
root.val = self.predecessor(root)
root.left = self.deleteNode(root.left, root.val)

return root```

Time Complexity: O(logN), where N is the number of nodes.
Space Complexity: O(H), for recursion stack, where H is the height of the BST.

## FAQs

Q. Why is the time complexity log(N)?
A. Since the given tree is a BST, we need to traverse the right subtree or left subtree at any given point. Hence, the time complexity is log(N).

Q. What is the most efficient approach to solving this problem?
A. The recursive approach is the most efficient approach to solve the problem. The time complexity is O(logN) and the space complexity is O(H).

##### Previous Post ## Find Median in a Stream

##### Next Post 