Formatted question description: https://leetcode.ca/all/450.html
450. Delete Node in a BST (Medium)
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.
Note: Time complexity should be O(height of tree).
Example:
root = [5,3,6,2,4,null,7] key = 3 5 / \ 3 6 / \ \ 2 4 7 Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the following BST. 5 / \ 4 6 / \ 2 7 Another valid answer is [5,2,6,null,4,null,7]. 5 / \ 2 6 \ \ 4 7
Companies:
Microsoft, Google, Amazon
Related Topics:
Tree
Solution 1.
// OJ: https://leetcode.com/problems/delete-node-in-a-bst/
// Time: O(H)
// Space: O(H)
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return NULL;
if (root->val > key) root->left = deleteNode(root->left, key);
else if (root->val < key) root->right = deleteNode(root->right, key);
else if (root->left) {
auto p = root->left;
while (p->right) p = p->right;
root->val = p->val;
root->left = deleteNode(root->left, root->val);
} else if (root->right) {
auto p = root->right;
while (p->left) p = p->left;
root->val = p->val;
root->right = deleteNode(root->right, root->val);
} else {
delete root;
root = NULL;
}
return root;
}
};
Solution 2.
// OJ: https://leetcode.com/problems/delete-node-in-a-bst/
// Time: O(H)
// Space: O(H)
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return NULL;
if (root->val > key) root->left = deleteNode(root->left, key);
else if (root->val < key) root->right = deleteNode(root->right, key);
else if (!root->left) {
auto right = root->right;
delete root;
return right;
} else if (!root->right) {
auto left = root->left;
delete root;
return left;
} else {
auto node = root->right;
while (node->left) node = node->left;
root->val = node->val;
root->right = deleteNode(root->right, root->val);
}
return root;
}
};
Java
-
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode deleteNode(TreeNode root, int key) { if (root == null) return root; if (root.val == key) { TreeNode dummyRoot = new TreeNode(0); dummyRoot.left = root; if (root.right != null) { TreeNode successor = root.right; if (successor.left == null) { successor.left = root.left; dummyRoot.left = successor; } else { TreeNode parent = successor, child = successor.left; while (child.left != null) { child = child.left; parent = parent.left; } root.val = child.val; parent.left = child.right; } } else dummyRoot.left = root.left; return dummyRoot.left; } else { TreeNode parent = root; TreeNode child = root.val > key ? root.left : root.right; while (child != null && child.val != key) { parent = child; child = child.val > key ? child.left : child.right; } if (child != null) { boolean isLeftChild = parent.left == child; if (child.left == null && child.right == null) { if (isLeftChild) parent.left = null; else parent.right = null; } else if (child.left == null) { if (isLeftChild) parent.left = child.right; else parent.right = child.right; } else if (child.right == null) { if (isLeftChild) parent.left = child.left; else parent.right = child.left; } else { TreeNode temp1 = child.right; if (temp1.left == null) { child.val = temp1.val; child.right = temp1.right; } else { TreeNode temp2 = temp1.left; while (temp2.left != null) { temp2 = temp2.left; temp1 = temp1.left; } child.val = temp2.val; temp1.left = temp2.right; } } } return root; } } }
-
// OJ: https://leetcode.com/problems/delete-node-in-a-bst/ // Time: O(H) // Space: O(H) class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if (!root) return NULL; if (root->val > key) root->left = deleteNode(root->left, key); else if (root->val < key) root->right = deleteNode(root->right, key); else if (root->left) { auto p = root->left; while (p->right) p = p->right; root->val = p->val; root->left = deleteNode(root->left, root->val); } else if (root->right) { auto p = root->right; while (p->left) p = p->left; root->val = p->val; root->right = deleteNode(root->right, root->val); } else { delete root; root = NULL; } return root; } };
-
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def deleteNode(self, root, key): """ :type root: TreeNode :type key: int :rtype: TreeNode """ def delete(root, pre): if root.right: p = root.right while p.left: p = p.left p.left = root.left if root is pre.left: pre.left = root.right or root.left if root is pre.right: pre.right = root.right or root.left root.left = None if not root: return root pre = dummy = TreeNode(float("inf")) dummy.left = root p = dummy while p: if key > p.val: pre = p p = p.right elif key < p.val: pre = p p = p.left else: delete(p, pre) break return dummy.left