Introduction to Tries

A Trie (also known as a prefix tree) is a tree-like data structure that is used to store a dynamic set of strings. Tries are commonly used for implementing autocomplete features, spell checkers, and IP routing tables.

Interactive Trie Visualization

The visualization below demonstrates the structure and functionality of a Trie. You can insert, search for, and find all words with a given prefix to see how the Trie works.

Trie Data Structure

Legend

Current Node

End of Word

Regular Node

Trie Properties

• Each node represents a character

• Root to leaf path forms a word

• Efficient prefix matching: O(m)

• Space-efficient for common prefixes

Sample Words in Trie

Words: cat, car, card, care, careful, cats, dog, dodge, door, down

Trie Data Structure

A Trie, also known as a prefix tree, is a tree-like data structure that stores a dynamic set of strings. Tries are commonly used for efficient prefix matching and searching.

Insertion Algorithm

Start at the root of the trie.
For each character in the word, check if a child node corresponding to the character exists.
If it doesn't exist, create a new node.
Move to the child node.
After the last character, mark the current node as the end of a word.

Search Algorithm

Start at the root of the trie.
For each character in the word, check if a child node corresponding to the character exists.
If it doesn't exist, the word is not in the trie.
Move to the child node.
After the last character, check if the current node is marked as the end of a word.

Trie Implementation


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

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

    def insert(self, word: str) -> None:
        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

    def search(self, word: str) -> bool:
        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