Trie

What is a Trie?

A Trie (pronounced as "try") is a tree-based data structure that stores strings efficiently for fast search, insertion, and deletion. Each node represents a single character, and paths in the tree represent words. Tries are particularly useful for prefix-based problems, such as autocomplete and dictionary lookups.

How a Trie Works

Each node in a Trie contains:

1. Character: The value stored in the node.
2. Children: References to child nodes (next characters in the word).
3. End of Word Marker: A flag to indicate if the node marks the end of a word.

Tries build words character by character, where a single root node branches out for each possible starting character.

Here’s an example of how the Trie looks after inserting the words: cat, cap, bat, and bad.

Key Operations on a Trie

Insertion O(m)

Inserts a word character by character. If a character doesn't exist as a child, it creates a new node.

Search O(m)

Checks if a word exists by traversing the tree character by character.

Prefix Matching O(p + n)

Efficiently finds all words starting with a given prefix.

Applications of Tries

Tries are widely used in:

• Autocomplete systems (like search engines and text editors).
• Spell checkers and dictionary lookups.
• IP routing (used in networking).
• Pattern matching for strings and text processing.

Tries are efficient for operations involving prefixes, making them indispensable in various real-world applications.

Code Examples

Here are examples of basic Trie operations in Python, C++, and Java.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    # Insert a word into the Trie
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    # Search for a word in the Trie
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    # Check if any word starts with a given prefix
    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

# Example usage
trie = Trie()
trie.insert("cat")
trie.insert("cap")
trie.insert("bat")
trie.insert("bad")

print(trie.search("cat"))  # Output: True
print(trie.starts_with("ba"))  # Output: True

Problems to Solve

Important Problems on Tries

Resources

• Trie Data Structure by Tushar Roy
• Trie data structure - Inside code
• Trie Series | Striver