Code Example
final class BSTNode<Value: Comparable> {
var val: Value?
var left: BSTNode?
var right: BSTNode?
init(val: Value? = nil) {
self.val = val
}
func exists(_ val: Value) -> Bool {
// 1
guard let selfVal = self.val else { return false }
// 2
if self.val == val {
return true
}
// 3
if val < self.val! {
if self.left == nil {
return false
}
return self.left!.exists(val)
}
// 4
if self.right == nil {
return false
}
// 5
return self.right!.exists(val)
}
}
Implementation
The exists
algorithm:
- Check if
self.val
exists. If it does not exist, returnfalse
. If it does, move to the next step. - Compare
self.val
with the input value. If the values are equal, returntrue
. If they are not equal, move to the next step. - If the input
val
is less thanself.val
, and theleft
node exists, return a recursive call of theexists
method on theleft
node; otherwise, returnfalse
. If the inputval
is greater thanself.val
, move to the next step. - Check if the
right
node exists. If it does not exist, returnfalse
. If it does exist, move to the next step. - Return a recursive call of the
exists
method on theright
node.
Time/Space Complexity
- Time complexity: The time complexity of the
exists
algorithm is O(N), where N is the total number of nodes. - Space complexity:
- O(1) if recursion stack space is not considered.
- Otherwise, O(H), where H is the height of the tree.
- In the worst case, H can be the same as N (when the tree is skewed).
- In the best case, H can be the same as log N (when the tree is complete).