- Problem Statement<\/a><\/li>
- Approach: Recursion<\/a><\/li>
- Case 1:<\/a><\/li>
- Case 2:<\/a><\/li>
- Case 3:<\/a><\/li><\/ul>
- Implementation<\/a><\/li>
- C++ Code<\/a><\/li>
- Java Code<\/a><\/li>
- Python Code<\/a><\/li><\/ul>
- FAQs<\/a><\/li>
- Q.1: Why is the time complexity log(N)?<\/a><\/li>
- Q.2: What is the most efficient approach to solving this problem?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
Problem Statement<\/h2>\n\n\n\n
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.<\/p>\n\n\n\n
Examples:<\/strong>
Input:<\/strong><\/p>\n\n\n\n<\/figure>\n\n\n\n
Key =<\/strong> 3
Output:<\/strong> Shown in the image<\/p>\n\n\n\nApproach: Recursion<\/h2>\n\n\n\n
If you observe clearly, there are mainly three possible conditions.<\/p>\n\n\n\n
Case 1:<\/h3>\n\n\n\n
- If the key to be deleted is a leaf node:
- In this case, simply make the node NULL.<\/li><\/ul><\/li><\/ul>\n\n\n\n
Case 2:<\/h3>\n\n\n\n
- 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.<\/li><\/ul><\/li><\/ul>\n\n\n\n
Case 3:<\/h3>\n\n\n\n
- 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.<\/li><\/ul><\/li><\/ul>\n\n\n\n
Algorithm<\/strong><\/p>\n\n\n\n
- Compare the value of the key<\/strong> with the value<\/strong> of the root. If the key > root -> value, recursively traverse the right subtree.<\/li>
- If key < root -> value, recursively traverse the left subtree.<\/li>
- While traversing if key == root->value, we need to delete this node:
- If the node is a leaf, make root = NULL.<\/li>
- 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.<\/li>
- 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.<\/li><\/ul><\/li>
- Return root<\/li><\/ul>\n\n\n\n
Implementation<\/h2>\n\n\n\n
C++ Code<\/h3>\n\n\n\n
int successor(TreeNode * root) {\n root = root -> right;\n while (root -> left != NULL) root = root -> left;\n return root -> val;\n}\nint predecessor(TreeNode * root) {\n root = root -> left;\n while (root -> right != NULL) root = root -> right;\n return root -> val;\n}\n \nTreeNode * deleteNode(TreeNode * root, int key) {\n if (root == NULL) return NULL;\n if (key > root -> val) root -> right = deleteNode(root -> right, key);\n else if (key < root -> val) root.left = deleteNode(root -> left, key);\n else {\n if (root -> left == NULL && root -> right == NULL) root = NULL;\n else if (root -> right != NULL) {\n root -> val = successor(root);\n root.right = deleteNode(root -> right, root -> val);\n } else {\n root -> val = predecessor(root);\n root -> left = deleteNode(root -> left, root -> val);\n }\n }\n return root;\n}<\/pre>\n\n\n\nJava Code<\/h3>\n\n\n\n
int successor(TreeNode * root) {\n root = root -> right;\n while (root -> left != NULL) root = root -> left;\n return root -> val;\n}\nint predecessor(TreeNode * root) {\n root = root -> left;\n while (root -> right != NULL) root = root -> right;\n return root -> val;\n}\n \nTreeNode * deleteNode(TreeNode * root, int key) {\n if (root == NULL) return NULL;\n if (key > root -> val) root -> right = deleteNode(root -> right, key);\n else if (key < root -> val) root.left = deleteNode(root -> left, key);\n else {\n if (root -> left == NULL && root -> right == NULL) root = NULL;\n else if (root -> right != NULL) {\n root -> val = successor(root);\n root.right = deleteNode(root -> right, root -> val);\n } else {\n root -> val = predecessor(root);\n root -> left = deleteNode(root -> left, root -> val);\n }\n }\n return root;\n}\n}<\/pre>\n\n\n\nPython Code<\/h3>\n\n\n\n
class Solution:\n def successor(self, root):\n root = root.right\n while root.left:\n root = root.left\n return root.val\n \n def predecessor(self, root):\n root = root.left\n while root.right:\n root = root.right\n return root.val\n \n def deleteNode(self, root: TreeNode, key: int) -> TreeNode:\n if not root:\n return None\n \n if key > root.val:\n root.right = self.deleteNode(root.right, key)\n elif key < root.val:\n root.left = self.deleteNode(root.left, key)\n else:\n if not (root.left or root.right):\n root = None\n elif root.right:\n root.val = self.successor(root)\n root.right = self.deleteNode(root.right, root.val)\n else:\n root.val = self.predecessor(root)\n root.left = self.deleteNode(root.left, root.val)\n \n return root<\/pre>\n\n\n\n
Time Complexity:<\/strong> O(logN), where N is the number of nodes.
Space Complexity:<\/strong> O(H), for recursion stack, where H is the height of the BST.<\/p>\n\n\n\nFAQs<\/h2>\n\n\n\n
Q.1: Why is the time complexity log(N)?<\/span><\/h3>\n\n\n\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).<\/p>\n\n\n\n
Q.2: What is the most efficient approach to solving this problem?<\/span><\/h3>\n\n\n\n
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).<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a binary search tree and a key value. The task is to delete the given…\n","protected":false},"author":5,"featured_media":5106,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[678],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4857"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=4857"}],"version-history":[{"count":8,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4857\/revisions"}],"predecessor-version":[{"id":20691,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4857\/revisions\/20691"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/5106"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=4857"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=4857"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=4857"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
- Compare the value of the key<\/strong> with the value<\/strong> of the root. If the key > root -> value, recursively traverse the right subtree.<\/li>
- In this case, replace the node with its predecessor node.<\/li><\/ul><\/li><\/ul>\n\n\n\n
- 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 successor node.<\/li><\/ul><\/li><\/ul>\n\n\n\n
- If the key to be deleted is not a leaf and has the right child.
- In this case, simply make the node NULL.<\/li><\/ul><\/li><\/ul>\n\n\n\n
- Q.2: What is the most efficient approach to solving this problem?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
- Java Code<\/a><\/li>
- Case 2:<\/a><\/li>
- Approach: Recursion<\/a><\/li>
![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Input1-1024x386.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Recursion-Ex-1024x645.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-5-1024x401.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image4-1-1024x418.png\")
<\/figure>\n\n\n\n