ContactTrie.swift

class ContactsTree {

    var root: Node


    init() {
        root = Node(Character("\0"))
        root.isRoot = true
    }


    func insert(_ word: String) {
        var cursor = root
        for char in word {
            let newChar = Node(char)
            if cursor.children[char] == nil {
                cursor.children[char] = newChar
            }
            if let nextNode = cursor.children[char] {
                cursor = nextNode
            }
        }
        cursor.isWord = true
    }


    func searchForWord(_ word: String) -> [String] {
        var matchingWords = [String]()

        var list = [Character]()
        var wordList = [String]()
        let head = getNode(word)
        head?.isRoot = true

        inorder(head, &list, &wordList)
        matchingWords = wordList.filter { !$0.isEmpty }.map { word + $0 }
        return matchingWords
    }

    private func inorder(_ head: Node?,
                         _ list: inout [Character],
                         _ words: inout [String]) -> [Character] {
        guard let head = head else { return [Character]() }

        if !head.isRoot { list.append(head.char) }

        if head.isWord {
            var word = ""
            for char in list {
                word += String(char)
            }
            list.removeAll()
            words.append(word)
        }

        for child in head.children {
            inorder(child.value, &list, &words)
        }

        return list
    }

    private func getNode(_ word: String) -> Node? {
        var cursor = root

        for char in word {
            if let next = cursor.children[char] {
                cursor = next
            } else {
                return nil
            }
        }
        return cursor
    }

    class Node {
        var children = [Character: Node]()
        var char: Character
        var isWord = false
        var isRoot = false

        init(_ char: Character) {
            self.char = char
        }
    }
}

 let contactTree = ContactsTree()
for name in ["Abigail Williams",
             "Anne Hathaway",
             "Benjamin Button",
             "Carly Shay",
             "Chandler Bing",
             "Christopher Robin",
             "Dani Lee",
             "Edward Cullen",
             "Joey Tribbiani",
             "Monica Geller",
             "Phoebe Buffet",
             "Rachel Green",
             "Ross Geller"] {
    contactTree.insert(name)
}
contactTree.searchForWord("Ch")
contactTree.searchForWord("C")
contactTree.searchForWord("1")
contactTree.searchForWord("$")
contactTree.searchForWord("")