Chapters

Hide chapters

Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

15. Binary Search Tree Challenges
Written by Kelvin Lau

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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.
© 2024 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now