Home iOS & Swift Books Data Structures & Algorithms in Swift

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 scrambled text.

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.

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:

© 2021 Razeware LLC

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.