Tries

Similar to binary search trees, trie data structures also organize information in a logical hierarchy. Often pronounced “try”, the term comes from the English language verb to retrieve. While most algorithms are designed to manipulate generic data, tries are commonly used with strings. In this chapter, we’ll review trie structures and will implement our own trie model with Swift.


HOW IT WORKS

As discussed, tries organize data in a hierarchy. To see how they work, let’s build a dictionary that contains the following words:

Ball
Balls
Ballard
Bat
Bar
Cat
Dog

At first glance, we see words prefixed with the phrase “Ba”, while entries like “Ballard” combine words and phrases (e.g., “Ball” and “Ballard”). Even though our dictionary contains a limited quantity of words, a thousand-item list would have the same properties. As with any algorithm, we’ll apply our knowledge to build an efficient model. To start, let’s create a new trie for the word “Ball”:

Tries involve building hierarchies, storing phrases along the way until a word is created (seen in yellow). With so many permutations, it’s important to know what qualifies as an actual word. For example, even though we’ve stored the phrase “Ba”, it’s not identified as a word. To see the significance, consider the next example:

As shown, we've traversed the structure to store the word "Bat". The trie has allowed us to reuse the permutations of "B" and "Ba" added by the inclusion of the word "Ball". Though most algorithms are measured on time efficiency, tries demonstrate great efficiency with time and space. Practical implementations of tries can be seen in modern software features like auto-complete, search engines and spellcheck.


THE DATA STRUCTURE

Here’s an example of a trie data structure written in Swift. In addition to storing a key, the structure also includes an Array for identifying its children. Unlike a binary search tree, a trie can store an unlimited number of leaf nodes. The boolean value isFinal will allow us to distinguish words and phrases. Finally, the level will indicate the node’s level in a hierarchy.

//basic trie data structure

public class TrieNode {
    
    var key: String!
    var children: Array<TrieNode>
    var isFinal: Bool
    var level: Int

    init() {
        self.children = Array<TrieNode>()
        self.isFinal = false
        self.level = 0
    }
    
}


ADDING WORDS

Here’s an algorithm that adds words to a trie. Although most tries are recursive structures, our example employs an iterative technique. The while loop compares the keyword length with the current node’s level. If no match occurs, it indicates additional keyword phases remain to be added.

    //build tree of dictionary content
    
    func addWord(keyword: String) {

        guard keyword.length > 0 else {
            return
        }
        
        var current: TrieNode = root
        
        while (keyword.length != current.level) {
            
            var childToUse: TrieNode!
            let searchKey: String = keyword.substringToIndex(current.level + 1)
                        
            //iterate through the node children
            for child in current.children {
                
                if (child.key == searchKey) {
                    childToUse = child
                    break
                }                
            }
            
            
            //create a new node
            if  (childToUse == nil) {
                
                childToUse = TrieNode()
                childToUse.key = searchKey
                childToUse.level = current.level + 1
                current.children.append(childToUse)
            }            
            
            current = childToUse
                       
        } //end while
        
        
        //final end of word check
        if (keyword.length == current.level) {
            current.isFinal = true
            print("end of word reached!")
            return
        }
        
    }
    

A final check confirms our keyword after completing the while loop. As part of this final check, we update the current node with the isFinal indicator. As mentioned, this step will allow us to distinguish words from phrases.


FINDING WORDS

The algorithm for finding words is similar to adding content. Again, we establish a while loop to navigate the trie hierarchy. Since the goal will be to return a list of possible words, these will be tracked using an Array.

    //find all words based on the prefix
    
    func findWord(keyword: String) -> Array<String>! {
        
        guard keyword.length > 0 else {
            return nil
        }        
        
        var current: TrieNode = root
        var wordList: Array<String> = Array<String>()
        
        while (keyword.length != current.level) {
            
            var childToUse: TrieNode!
            let searchKey: String = keyword.substringToIndex(current.level + 1)
            
            //iterate through any children
            for child in current.children {
                
                if (child.key == searchKey) {
                    childToUse = child
                    current = childToUse
                    break
                }
                
            }            
 
            if childToUse == nil {
               return nil
            }            
            
        } //end while
                
        
        //retrieve the keyword and any decendants
        if ((current.key == keyword) && (current.isFinal)) {
            wordList.append(current.key)
        }
        
        //include only children that are words
        for child in current.children {
            
            if (child.isFinal == true) {
                wordList.append(child.key)
            }            
        }        
        
        return wordList
        
    } //end function
    

The findWord function checks to ensure keyword phrase permutations are found. Once the entire keyword is identified, we start the process of building our word list. In addition to returning keys identified as words (e.g., “Bat”, “Ball”), we account for the possibility of returning nil by returning an implicit unwrapped optional.


EXTENDING SWIFT

Even though we’ve written our trie in Swift, we’ve extended some language features to make things work. Commonly known as categories in Objective-C, our algorithms employ two additional Swift extensions. The following class extends the functionality of the native String class:

//extend the native String class

extension String {
  
   //compute the length
    var length: Int {
        return self.characters.count
    }
    
    
    //returns characters up to a specified index
    func substringToIndex(to: Int) -> String {
        return self.substringToIndex(self.startIndex.advancedBy(to))
    }

      
}

Like this series? Subscribe to the newsletter and receive a free guide on iOS interview tips.