Delete

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: ...