Tries (Prefix Trees)

Overview

A Trie, also known as a prefix tree, is a specialized tree used to store associative data structures where the keys are usually strings. It is particularly effective for solving problems involving prefix matching, autocomplete systems, and dictionaries.

Key Characteristics

• Each node in the trie represents a single character of a string.

• The root is typically an empty node.

• Paths from the root to leaf nodes form words.

• Supports fast insert, search, and prefix operations.

Time Complexity

Where n is the length of the word or prefix.

Swift Implementation

TrieNode Definition

class TrieNode {
    var children: [Character: TrieNode] = [:]
    var isEndOfWord: Bool = false
}

Trie Class

class Trie {
    private let root = TrieNode()

    func insert(_ word: String) {
        var current = root
        for char in word {
            if current.children[char] == nil {
                current.children[char] = TrieNode()
            }
            current = current.children[char]!
        }
        current.isEndOfWord = true
    }

    func search(_ word: String) -> Bool {
        guard let node = findNode(for: word) else { return false }
        return node.isEndOfWord
    }

    func startsWith(_ prefix: String) -> Bool {
        return findNode(for: prefix) != nil
    }

    private func findNode(for string: String) -> TrieNode? {
        var current = root
        for char in string {
            guard let next = current.children[char] else { return nil }
            current = next
        }
        return current
    }
}

Example Usage

let trie = Trie()
trie.insert("apple")
trie.insert("app")
trie.insert("banana")

print(trie.search("app"))       // true
print(trie.search("appl"))      // false
print(trie.startsWith("ban"))   // true
print(trie.startsWith("bat"))   // false

Visual Example

After inserting the words apple and app, the trie looks like:

(root)
  └── a
      └── p
          └── p (✓)
              └── l
                  └── e (✓)

• A checkmark (✓) represents isEndOfWord = true.

Applications of Tries

• Autocomplete systems

• Spell checkers

• IP routing

• T9 predictive text

• Word games like Boggle and Scrabble

Summary

Tries provide an efficient solution for prefix-based problems. They are especially useful when working with large dictionaries or needing rapid lookup for partially typed words. While they may use more memory than other data structures, the performance benefits in specific scenarios often outweigh the cost.