## 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 the image

## Approach: Recursion

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

### Case 1:

- If the key to be deleted is a leaf node:
- In this case, simply make the node NULL.

### Case 2:

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

### Case 3:

- 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 the
**key**with the**value**of the 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 a left child, but not a right child, recursively replace its value with a predecessor node and delete its predecessor from its original position.

- Return root

## Implementation

### 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.1: Why is the time complexity log(N)?

Ans. 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.2: What is the most efficient approach to solving this problem?

Ans. The recursive approach is the most efficient approach to solving the problem. The time complexity is O(logN) and the space complexity is O(H).