Swift Algorithm Club: Swift Binary Search Tree Data Structure

Copy on Write

Though this is a great implementation, it won't work. Test this by writing the following at the end of your playground:

var binaryTree: BinaryTree<Int> = .empty
binaryTree.naiveInsert(newValue: 5) // binaryTree now has a node value with 5
binaryTree.naiveInsert(newValue: 7) // binaryTree is unchanged
binaryTree.naiveInsert(newValue: 9) // binaryTree is unchanged

Copy-on-write is the culprit here. Every time you try to mutate the tree, a new copy of the child is created. This new copy is not linked with your old copy, so your initial binary tree will never be updated with the new value.

This calls for a different way to do things. Write the following at the end of the BinaryTree enum:

private func newTreeWithInsertedValue(newValue: T) -> BinaryTree {
  switch self {
  // 1
  case .empty:
    return .node(.empty, newValue, .empty)
  // 2 
  case let .node(left, value, right):
    if newValue < value {
      return .node(left.newTreeWithInsertedValue(newValue: newValue), value, right)
    } else {
      return .node(left, value, right.newTreeWithInsertedValue(newValue: newValue))
    }
  }
}

This is a method that returns a new tree with the inserted element. The code is relatively straightforward:

1. If the tree is empty, you want to insert the new value here.
2. If the tree isn't empty, you'll need to decide whether to insert into the left or right child.

Write the following method inside your BinaryTree enum:

mutating func insert(newValue: T) {
  self = newTreeWithInsertedValue(newValue: newValue)
}

Test your code by replacing the test lines at the bottom of your playground:

binaryTree.insert(newValue: 5) 
binaryTree.insert(newValue: 7) 
binaryTree.insert(newValue: 9) 

You should end up with the following tree structure:

value: 5, 
    left = [], 
    right = [value: 7, 
        left = [], 
        right = [value: 9, 
            left = [], 
            right = []]]

Congratulations - now you've got insertion working!

Insertion Time Complexity

As discussed in the spoiler section, you need to create a new copy of the tree every time you make an insertion. Creating a new copy requires going through all the nodes of the previous tree. This gives the insertion method a time complexity of O(n).

Traversal Algorithms

Traversal algorithms are fundamental to tree related operations. A traversal algorithm goes through all the nodes in a tree. There are three main ways to traverse a binary tree:

In-order Traversal

In-order traversal of a binary search tree is to go through the nodes in ascending order. Here's what it looks like to perform an in-order traversal:

Starting from the top, you head to the left as much as you can. If you can't go left anymore, you'll visit the current node and attempt to traverse to the right side. This procedure continues until you traverse through all the nodes.

Write the following inside your BinaryTree enum:

func traverseInOrder(process: @noescape (T) -> ()) {
  switch self {
  // 1
  case .empty:
    return 
  // 2
  case let .node(left, value, right):
    left.traverseInOrder(process: process)
    process(value)
    right.traverseInOrder(process: process)
  }
}

This code is fairly straightforward:

1. If the current node is empty, there's no way to go down further. You'll simply return here.
2. If the current node is non empty, then you can go down further. The definition of in-order traversal is to go down the left side, visit the node, and then the right side.

To see this in action, you'll create the binary tree shown above. Delete all the test code at the bottom of your playground and replace it with the following:

var tree: BinaryTree<Int> = .empty
tree.insert(newValue: 7)
tree.insert(newValue: 10)
tree.insert(newValue: 2)
tree.insert(newValue: 1)
tree.insert(newValue: 5)
tree.insert(newValue: 9)

tree.traverseInOrder { print($0) }

You've created a binary search tree using your insert method. traverseInOrder will go through your nodes in ascending order, passing the value in each node to the trailing closure.

Inside the trailing closure, you're printing the value that was passed in by the traversal method. $0 is a shorthand syntax that references the parameter that is passed in to the closure.

You should see the following output in your console:

1
2
5
7
9
10

Pre-order Traversal

Pre-order traversal of a binary search tree is to go through the nodes whilst visiting the current node first. The key here is calling process before traversing through the children. Write the following inside your BinaryTree enum:

func traversePreOrder( process: @noescape (T) -> ()) {
  switch self {
  case .empty:
    return
  case let .node(left, value, right):
    process(value)
    left.traversePreOrder(process: process)
    right.traversePreOrder(process: process)
  }
}

Post-order Traversal

Post-order traversal of a binary search tree is to visit the nodes only after traversing through it's left and right children. Write the following inside your BinaryTree enum:

func traversePostOrder( process: @noescape (T) -> ()) {
  switch self {
  case .empty:
    return
  case let .node(left, value, right):
    left.traversePostOrder(process: process)
    right.traversePostOrder(process: process)
    process(value) 
  }
}

These 3 traversal algorithms serve as a basis for many complex programming problems. Understanding them will prove useful for many situations, including your next programming interview!

Mini Challenge

What is the time complexity of the traversal algorithms?

[spoiler title="Solution"]
The time complexity is O(n), where n is the number of nodes in the tree.

This should be obvious, since the idea of traversing a tree is to go through all the nodes!
[/spoiler]

Searching

As the name suggests, a binary search tree is known best for facilitating efficient searching. A proper binary search tree will have all it's left children less than it's parent node, and all it's right children equal to or greater than it's parent node.

By exploiting this guarantee, you'll be able to determine which route to take - the left child, or the right child - to see if your value exists within the tree. Write the following inside your BinaryTree enum:

func search(searchValue: T) -> BinaryTree? {
  switch self {
  case .empty:
    return nil
  case let .node(left, value, right):
    // 1
    if searchValue == value {
      return self
    }
 
    // 2
    if searchValue < value {
      return left.search(searchValue: searchValue)
    } else {
      return right.search(searchValue: searchValue)
    }
  }
}

Much like the traversal algorithms, searching involves traversing down the binary tree:

1. If the current value matches the value you're searching for, you're done searching. Return the current subtree
2. If execution continues to this point, it means you haven't found the value. You'll need to decide whether you want to go down to the left or right. You'll decide using the rules of the binary search tree.

Unlike the traversal algorithms, the search algorithm will traverse only 1 side at every recursive step. On average, this leads to a time complexity of O(log n), which is considerably faster than the O(n) traversal.

You can test this by adding the following to the end of your playground:

tree.search(searchValue: 5)