Introduction
The delete algorithm is perhaps one of the hardest parts of managing a binary search tree (BST).
Code Example
final class BSTNode {
var val: Int?
var left: BSTNode?
var right: BSTNode?
init(val: Int? = nil) {
self.val = val
}
func delete(_ val: Int) -> BSTNode? {
// 1
guard let selfVal = self.val else {
return nil
}
// 2
if val < selfVal {
if self.left == nil {
return self
}
self.left = self.left!.delete(val)
}
// 3
if val > selfVal {
if self.right == nil {
return self
}
self.right = self.right!.delete(val)
}
// 4
if self.right == nil {
return self.left
}
// 5
if self.left == nil {
return self.right
}
// 6
var minLargerNode = self.right
while minLargerNode?.left != nil {
minLargerNode = minLargerNode?.left
}
guard let minLargerNode = minLargerNode else {
return self
}
self.val = minLargerNode.val
self.right = self.right?.delete(minLargerNode.val!)
return self
}
}
Implementation
Let’s look at the details:
- The first step is to check for the base scenario: whether the BST has a
self.val
. If it does not, returnnil
. If it has a value, move to the second step. - The second step is to check if the delete value is less than
self.val
. If it is, check if the left node exists. If it does not exist, return theself
node. If it does exist, calldelete
on the left node and assign the new result to theleft
node. - The third step is the opposite of the second step but for the right node.
- The fourth step is to check if the
right
node isnil
. If it is, return theleft
node. - The fifth step is the opposite of the fourth but for the
left
andright
nodes. - The sixth step is to find the
minLargerNode
, updateself.val
withminLargerNode.val
, and deleteminLargerNode.val
from theright
node, assigning the new result to it.
Time Complexity
The time complexity of the BST deletion algorithm is O(h), where h
is the height of the tree.
In the case where the BST becomes skewed, the height of the BST h
becomes O(n), making the time complexity O(n).
In the case where the BST is balanced, the height of the BST h
becomes O(log n), making the time complexity O(log n).