# 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 have searching of binary trees down cold? 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 conform 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.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below: