15. Binary Search Tree Challenges

Written by Kelvin Lau

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.

An algorithm that verifies whether a tree is a binary search tree involves going through all the nodes and checking for this property.

Write the following in your playground page:

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 else {
      return true
    }

    // 3
    if let min, tree.value <= min {
      return false
    } else if let max, tree.value > max {
      return false
    }

    // 4
    return isBST(tree.leftChild, min: min, max: tree.value) &&
           isBST(tree.rightChild, min: tree.value, max: max)
  }
}

isBinarySearchTree is the interface that will be exposed for external use. Meanwhile, the magic happens in the isBST function:

1. isBST is responsible for recursively traversing through the tree and checking for the BST property. It needs to keep track of progress via a reference to a BinaryNode, and also keep track of the min and max values to verify the BST property.
2. This is the base case. If tree is nil, then there are no nodes to inspect. A nil node is a binary search tree, so you’ll return true in that case.
3. This is essentially a bounds check. If the current value exceeds the bounds of the min and max, the current node violates binary search tree rules.
4. This line contains the recursive calls. When traversing through the left children, the current value is passed in as the max value. This is because any nodes on the left side cannot be greater than the parent. Vice versa, when traversing to the right, the min value is updated to the current value. Any nodes on the right side must be greater than the parent. If any of the recursive calls evaluate false, the false value will propagate back to the top.

The time complexity of this solution is O(n) since you need to traverse through the entire tree once. There is also a O(n) space cost since you’re making n recursive calls.

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: @retroactive Equatable where Element: Equatable {

  // 1
  public static func ==(lhs: BinarySearchTree,
                        rhs: BinarySearchTree) -> Bool {
    isEqual(lhs.root, rhs.root)
  }

  // 2
  private static func isEqual(
    _ 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)
  }
}

Here’s an explanation of the code:

1. This is the function that the Equatable protocol requires. Inside the function, you’ll return the result from the isEqual helper function.
2. isEqual will recursively check two nodes and their descendants for equality.
3. This is the base case. If one or more of the nodes are nil, then there’s no need to continue checking. If both nodes are nil, they are equal. Otherwise, one is nil and one isn’t nil, so they must not be equal.
4. Here, you check the value of the left and right nodes for equality. You also recursively check the left children and right children for equality.

The time complexity of this function is O(n). The space complexity of this function is O(n).

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

1. You’ll make use of a Set for this solution. To insert elements into a Set, the elements must be Hashable, so you first constrain the extension where Element is Hashable.
2. Inside the contains function, you begin by inserting all the elements of the current tree into the set.
3. isEqual is to store the end result. You need this because traverseInOrder takes a closure, and you cannot directly return from inside the closure.
4. For every element in the subtree, you check if the set contains the value. If at any point set.contains($0) evaluates as false, you’ll make sure isEqual stays false even if subsequent elements evaluate as true by assigning isEqual && set.contains($0) to itself.

The time complexity for this algorithm is O(n). The space complexity for this algorithm is O(n).