Swift Algorithm Club: Swift Trie Data Structure

Terminating Nodes

At this point, the insert method will correctly go through the word you want to insert and create new nodes as necessary. You might have noticed something though. For example, if you inserted the word "cute", how do can you tell if "cut" has been inserted or not?

Without some sort of indicator, you can't be sure. Head back to your TrieNode class. Update the class with a new property:

var isTerminating = false

The isTerminating property will be responsible for indicating the end of a word. Back to the previous example, if you insert the word "cute" into the Trie, you'll want to use isTerminating like this:

The last letter of "cute" is marked, indicating it's the end of the word. If you insert "cut" into the Trie, all you want to do is mark the "t" with as a terminating node:

Pretty easy? Try it out!

Challenge

At the end of the method, implement the logic to mark the last node as the terminating node.

[spoiler title="Solution"]

if currentIndex == characters.count {
  currentNode.isTerminating = true
}

If the currentIndex equals the number of letters of the word you're trying to add, it means you've reached the last letter. At that point, you'll flip isTerminating to true.
[/spoiler]

Contains

Now that you've got insertion set up, it's time to deal with the contains method. This method is responsible for checking if a word exists. Write the following into the extension:

func contains(word: String) -> Bool {
  guard !word.isEmpty else { return false }
  var currentNode = root

  let characters = Array(word.lowercased().characters)
  var currentIndex = 0

  // more to come
}

So far, the code you've just written is nearly identical to the insert method. Add the following to the bottom of the contains method:

// 1
while currentIndex < characters.count, let child = currentNode.children[characters[currentIndex]] {

  // 2
  currentIndex += 1
  currentNode = child
}

This part will try to iterate through the nodes of the Trie based on the word you're trying to find:

1. You create a while loop with the condition that the currentIndex hasn't reached the end of the word. You also try to bind the children dictionary's value into a child property.
2. If the while loop succeeds, you move currentIndex and currentNode to look for the next matching letter.

Iterating through the word is now taken care of. Finally, it's time to implement the logic that either returns true or false, depending on whether the word is inside the Trie. Write the following at the bottom of the contains method:

if currentIndex == characters.count && currentNode.isTerminating {
  return true
} else {
  return false
}

If the currentIndex variable reaches to the end of the characters array, it means the while loop has successfully gone through all the letters and the corresponding nodes. You'll also check if this last node is a terminating node. If both these conditions are true, then the word is in the Trie. If one of these conditions is false, then the word is not in the Trie.

Try it Out!

Write the following at the end of the playground:

let trie = Trie()

trie.insert(word: "cute") 
trie.contains(word: "cute") // true

trie.contains(word: "cut") // false
trie.insert(word: "cut") 
trie.contains(word: "cut") // true

With that, you're well on your way to mastering the art of the Trie!

Where To Go From Here?

I hope you enjoyed this tutorial on making a Swift Trie data structure!

Here is a Swift Playground with the above code. You can also find the original implementation and further discussion in the Swift Trie section of the Swift Algorithm Club repository.

This was just one of the many algorithm clubs focused on the Swift Algorithm Club repository. If you're interested in more, check out the repo.

It's in your best interest to know about algorithms and data structures - they're solutions to many real world problems, and are frequently asked as interview questions. Plus it's fun!

So stay tuned for many more tutorials from the Swift Algorithm club in the future. In the meantime, if you have any questions on implementing trees in Swift, please join the forum discussion below!

If you enjoyed what you learned in this tutorial, why not check out our Data Structures and Algorithms in Swift book, available on our store?

In Data Structures and Algorithms in Swift, you’ll learn how to implement the most popular and useful data structures and when and why you should use one particular datastructure or algorithm over another. This set of basic data structures and algorithms will serve as an excellent foundation for building more complex and special-purpose constructs.

As well, the high-level expressiveness of Swift makes it an ideal choice for learning these core concepts without sacrificing performance.

• You’ll start with the fundamental structures of linked lists, queues and stacks, and see how to implement them in a highly Swift-like way.
• Move on to working with various types of trees, including general purpose trees, binary trees, AVL trees, binary search trees and tries.
• Go beyond bubble and insertion sort with better-performing algorithms, including mergesort, radix sort, heap sort and quicksort.
• Learn how to construct directed, non-directed and weighted graphs to represent many real-world models, and traverse graphs and trees efficiently with breadth-first, depth-first, Dijkstra’s and Prim’s algorithms to solve problems such as finding the shortest path or lowest cost in a network.
• And much, much more!

By the end of this book, you’ll have hands-on experience solving common issues with data structures and algorithms — and you’ll be well on your way to developing your own efficient and useful implementations.