15 Binary Search Tree Challenges Written by Kelvin Lau

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

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
}
}
``````

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.