algorithms.live
    DSA
    intermediate

    Trie (Prefix Tree)

    Software Engineer path · lesson 18 of 99
    time O(L)
    space O(N*L)

    Syntax: insert word · search word · prefix word. Numbers from -99 to 99.

    Try:
    root
    New nodePathHereMatchEnd of word ★Missing

    Empty trie: just the root.

    Code (running line highlighted)
    1. 1insert(word): node = root
    2. 2 for ch in word: node = node.child[ch] (create it if missing)
    3. 3 node.is_word = true
    4. 4search(word): follow ch by ch; fail if a child is missing
    5. 5 return node.is_word # prefix(p): return true
    Character steps
    0 / 17
    Nodes created
    0 / 5
    Invariant: Every path from the root spells a prefix of some inserted word; shared prefixes share nodes.

    Tap any element in the diagram to inspect its state at this step.

    1 / 25

    Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.

    Insert "cat"

    Sequence

    Order the steps of inserting the word "cat" into a trie.

    Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.

    1. 1Drop a step here
    2. 2Drop a step here
    3. 3Drop a step here
    4. 4Drop a step here
    5. 5Drop a step here
    5 pieces left to place

    Test your knowledge

    21 questions
    Question 1 of 21
    Score: 0

    What is the Time Complexity of searching for a word of length L in a Trie?

    Write the code

    Runs your solution

    Implement Trie

    Implement a Trie with `insert`, `search`, and `startsWith` methods.

    Example Cases

    Input:const t = new Trie(); t.insert("apple"); return t.search("apple");
    Output:true
    Input:const t = new Trie(); t.insert("apple"); return t.search("app");
    Output:false
    Input:const t = new Trie(); t.insert("apple"); return t.startsWith("app");
    Output:true
    javascript
    class Trie {
  constructor() {}
  insert(word) {}
  search(word) {}
  startsWith(prefix) {}
}

    The short version

    Think of autocomplete on your phone. As you type 'A-P-P', it narrows down the massive dictionary to just the branch containing 'Apple', 'Appetizer', etc. efficient prefix lookup.

    In more depth

    The Prefix Tree

    A Trie (pronounced "try") is a tree-like data structure used for efficiently storing and retrieving keys in a dataset of strings.

    Why use it?

    It excels at prefix-based searches. If you want to find all words starting with "App", a Hash Map can't help you easily, but a Trie can do it in O(L) time where L is the length of the prefix.

    Structure:

    Each node represents a character. Paths from the root to a node represent a string prefix.

    When to reach for this

    • Autocomplete / Typeahead suggestions
    • Spell checker
    • Longest Common Prefix
    • Word Search strategies

    Interview Questions

    Google
    Microsoft
    Google
    Amazon
    Microsoft
    Uber
    Amazon
    Amazon
    Google
    Bloomberg
    Microsoft
    Uber
    Facebook

    References & Further Reading

    The Trie Data Structure (Prefix Tree)YouTube · Jacob Sorber
    video
    TrieWikipedia
    article
    Radix treeWikipedia
    article
    All Data Structures & Algorithms topics

    Love this visualization?

    Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.

    100% free • No credit card required