Trie (Prefix Tree)

    DSA · Intermediate

    Definition

    A trie is a tree where each edge is a character, so words sharing a prefix share a path.

    Powers autocomplete, spell check and prefix searches.

    Diagram

    rootc → a → t (end)c → a → r (end)

    Flowchart

    Start at rootFor each char, go to or create childMark end of wordSearch follows the same path

    Example: Insert and search

    root = {}
def insert(w):
    n = root
    for c in w:
        n = n.setdefault(c, {})
    n['#'] = True
def search(w):
    n = root
    for c in w:
        if c not in n: return False
        n = n[c]
    return '#' in n
insert('cat'); insert('car')
print(search('car'), search('ca'))

    Output: True False

    Complexity

    Insert/Search O(L) where L = word length

    Key points

    • Uses more memory than a hash set
    • Great for prefix queries

    Interview questions

    Trie vs hash set?

    A trie answers 'any word with this prefix?' efficiently; a hash set cannot.

    More DSA topics

    ArraysLinked ListStackQueue