15.
Binary Search Tree Challenges
Written by Kelvin Lau
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
Think you’ve gotten the hang of binary search trees? Try out these three challenges to lock the concepts down.
Challenge 1: Binary tree or binary search tree?
Create a function that checks if a binary tree is a binary search tree.
Challenge 2: Equatable
The binary search tree currently lacks Equatable conformance. Your challenge is to adopt the Equatable protocol.
Challenge 3: Is it a subtree?
Create a method that checks if the current tree contains all the elements of another tree. You may require that elements are Hashable.
Solutions
Solution to Challenge 1
A binary search tree is a tree where every left child is less than or equal to its parent, and every right child is greater than its parent.
extension BinaryNode where Element: Comparable {
var isBinarySearchTree: Bool {
isBST(self, min: nil, max: nil)
}
// 1
private func isBST(_ tree: BinaryNode<Element>?,
min: Element?,
max: Element?) -> Bool {
// 2
guard let tree = tree else {
return true
}
// 3
if let min = min, tree.value <= min {
return false
} else if let max = max, tree.value > max {
return false
}
// 4
return isBST(tree.leftChild, min: min, max: tree.value) &&
isBST(tree.rightChild, min: tree.value, max: max)
}
}
Solution to Challenge 2
Conforming to Equatable is relatively straightforward. For two binary trees to be equal, both trees must have the same elements in the same order. Here’s what the solution looks like:
extension BinarySearchTree: Equatable {
// 1
public static func ==(lhs: BinarySearchTree,
rhs: BinarySearchTree) -> Bool {
isEqual(lhs.root, rhs.root)
}
// 2
private static func isEqual<Element: Equatable>(
_ node1: BinaryNode<Element>?,
_ node2: BinaryNode<Element>?) -> Bool {
// 3
guard let leftNode = node1, let rightNode = node2 else {
return node1 == nil && node2 == nil
}
// 4
return leftNode.value == rightNode.value &&
isEqual(leftNode.leftChild, rightNode.leftChild) &&
isEqual(leftNode.rightChild, rightNode.rightChild)
}
}
Solution to Challenge 3
Your goal is to create a method that checks if the current tree contains all the elements of another tree. In other words, the values in the current tree must be a superset of the values of the other tree. Here’s what the solution looks like:
// 1
extension BinarySearchTree where Element: Hashable {
public func contains(_ subtree: BinarySearchTree) -> Bool {
// 2
var set: Set<Element> = []
root?.traverseInOrder {
set.insert($0)
}
// 3
var isEqual = true
// 4
subtree.root?.traverseInOrder {
isEqual = isEqual && set.contains($0)
}
return isEqual
}
}