- Does the key always exist in the tree?
- Are all the values in the tree unique?
- Is the answer unique?
Input:
10
/ \
5 15
/ \ / \
3 7 13 18
key = 5
Output:
10
/ \
7 15
/ / \
3 13 18
- The key is root, the root will be updated.
Input:
10
/ \
5 15
key = 10
Output:
15
/
5
or
5
\
15
- The key is not found in the tree.
We search the key by DFS, then we delete the node with that key when we find it (root.value == key) by the following rules:
- If the node is a leaf, we just return
nullto detach it. - If the node has only one child (non-null), we return that only one child.
- If the node has two children, we keep swapping down to leaf with predecessor or successor, then delete the leaf. We can choose the predecessor or successor, here we choose the successor. We swap the root value with successor (root was deleted by replacing with successor), and then delete the successor recursively because we have move sucessor to become new root, the original successor node is redundant now that we have to delete it.
fun deleteNode(root: TreeNode?, key: Int): TreeNode? {
if (root == null) return null
// Search for that key
if (root.`val` < key) {
root.right = deleteNode(root.right, key)
return root
} else if (key < root.`val`) {
root.left = deleteNode(root.left, key)
return root
} else {
// The key is found at root, then
// there are three cases:
// 1. Root is leaf
if (root.left == null && root.right == null) return null
// 2. Root has only one child: either left or right child
if (root.right == null) return root.left
if (root.left == null) return root.right
// 3. Root has two children
var successor = root.right
while (successor?.left != null) {
successor = successor.left
}
// Replace the current node with its successor (delete the root)
root.`val` = successor!!.`val`
// The original successor become redundant, so we have to seek the successor from root.right and delete it.
root.right = deleteNode(root.right, successor.`val`)
}
return root
}- Time Complexity:
O(n). - Space Complexity:
O(n).
Updated: This is similar to the recursive approach for the case that is null, leaf and one child, but it's more complicated for the case that has two children. Just understand the key idea above (swap with successor and delete the original successor) and the recursive approach.
The deletion operations considers the tree cases:
- Leaves (node has no child): It's easy to delete, just detach. (Like binary tree deletion)
- Node has one child: We splice out by modifying pointer from parent to its child.
- Node have two children: We perform the same operation as binary tree deletion, we keep moving down the
Xby swapping withXand its successor (its successor will never be the parent ofX, it never goes up), untilXreaches the leaf, then detach.
And there are some key points for the implementation, given the root of BST and the key, we have to delete the node with that key and return the updated root node:
- We don't have
parentpointer in real implementation or problem, so we have to update parent node as we search or swap with the node. - The node to delete is root or not will affect the result + how many child does the node to delete have will affect the implementation, all the combinations will be:
- The node is root, is leaf. (root updated, it becomes empty tree)
- The node is root, has only one child. (The only child will become the new root)
- The node is root, has two children.
- The node is NOT root, is leaf.
- The node is NOT root, has only one child.
- The node is NOT root, has two children.
- The
successor(node)is a little bit different from orignal binary tree's we don't look for the lowest ancestor (don't look up upward).
private var parent: TreeNode? = null
fun deleteNode(root: TreeNode?, key: Int): TreeNode? {
val nodeToRemove = searchNodeToRemove(root, key)
// Not found
if (nodeToRemove == null) return root
// To remove root
if (parent == null) {
// Case 1.
// [5]
// 5
if (nodeToRemove.left == null && nodeToRemove.right == null) return null
// Case 2.
// [1,2] or [1,nul,2]
// 1
if (nodeToRemove.left == null) return nodeToRemove.right
if (nodeToRemove.right == null) return nodeToRemove.left
}
// We leave the case that to delete root that has two children here
deleteNode(nodeToRemove)
return root
}
private fun searchNodeToRemove(root: TreeNode?, key: Int): TreeNode? {
var current: TreeNode? = root
while (current != null && current.`val` != key) {
parent = current
if (current.`val` > key) {
current = current.left
} else {
current = current.right
}
}
return current
}
private fun deleteNode(nodeToDelete: TreeNode?) {
if (nodeToDelete == null) return
// We use let {...} scope function to eliminate all null check of parent node
parent?.let { parent ->
// Leaf to delete, just detach.
if (nodeToDelete.left == null && nodeToDelete.right == null) {
if (nodeToDelete.`val` == parent!!.left?.`val`) {
parent.left = null
} else if (nodeToDelete.`val` == parent.right.`val`) {
parent.right = null
}
return
}
// Node to delete has one child only
if (nodeToDelete.left == null || nodeToDelete.right == null) {
// Determine the left or right child of the node to delete for splicing out
val child = if (nodeToDelete.left != null) nodeToDelete.left!! else nodeToDelete.right!!
if (nodeToDelete.`val` == parent.left?.`val`) {
parent.left = child
} else if (nodeToDelete.`val` == parent.right.`val`) {
parent.right = child
}
return
}
}
// Node to delete has two children, find the successor and swipe
parent = nodeToDelete
var successor = nodeToDelete.right!!
while (successor?.left != null) {
parent = successor
successor = successor.left!!
}
val temp = nodeToDelete.`val`
nodeToDelete.`val` = successor.`val`
successor.`val` = temp
// Keep moving down the node by swapping with its successor
deleteNode(successor)
}[50,30,70,null,40,60,80]
30
[50,30,70,null,40,60,80]
50
[1,null,2]
1
[5]
5
[5]
3There are recursive solution, but I can't get it.