**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.

- If the node is a leaf, make
- 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).