In this Leetcode Delete Node in a BST problem solution we have 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 deletion can be divided into two stages:
- Search for a node to remove.
- If the node is found, delete the node.
Problem solution in Python.
class Solution: def deleteNode(self, root: TreeNode, key: int) -> TreeNode: if not root: return root if root.val > key: root.left = self.deleteNode(root.left, key) return root elif root.val < key: root.right = self.deleteNode(root.right, key) return root else: # root.val == key if not root.right: return root.left smInRight = root.right # Find the smallest node of right subtree of root # and attach left subtree of root to left of the smallest node in right while smInRight.left: smInRight = smInRight.left smInRight.left = root.left return root.right
Problem solution in Java.
public TreeNode deleteNode(TreeNode root, int key) { if(root == null) return root; if(root.val == key){ if(root.right == null) return root.left; TreeNode curr = root.right; while(curr.left != null) curr = curr.left; curr.left = root.left; return root.right; }else if(root.val < key){ root.right = deleteNode(root.right, key); }else{ root.left = deleteNode(root.left, key); } return root; }
Problem solution in C++.
class Solution { public: TreeNode * deleteNode(TreeNode*& root, int key) { if (!root) { return NULL; } if (root->val == key) { if (root->right) { TreeNode* nextGt = NULL; findMin(root->right, nextGt); swap(root->val, nextGt->val); root->right = deleteNode(root->right, key); return root; } else { TreeNode* res = root->left; delete root; return res; } } else if (root->val < key) { root->right = deleteNode(root->right, key); return root; } else if (root->val > key) { root->left = deleteNode(root->left, key); return root; } else { return root; } } private: void findMin(TreeNode* root, TreeNode*& min) { if(!root){ return; } min = root; while (min && min->left) { min = min->left; } } };