Trie (Prefix Tree)

A Trie (pronounced “try”) is a tree-like data structure that stores a dynamic set of strings, where each node represents a common prefix. This ingenious structure turns prefix lookups from

O(N*M)

O(M)

where M is the word length - making it the go-to choice for autocomplete systems, spell checkers, and dictionary implementations.

Real-World Analogy

Think of a trie like an organized phone directory. Instead of storing each name separately, similar names share common pages:

All names starting with “A” are in one section
Within “A”, names starting with “An” share a subsection
“Anderson”, “Andrews”, and “Anthony” branch from “An”

This organization means finding a name takes time proportional to the name length, not the total number of entries. Just like a well-organized directory lets you flip directly to the right section, a trie lets you navigate directly to matching prefixes.

Visual Explanation

Here is how a trie stores the words “app”, “apple”, “apply”, and “apt”:

  flowchart TD
    ROOT((root))
    A((a))
    P1((p))
    P2((p))
    T((t*))
    L1((l))
    E((e*))
    Y((y*))
    P3((p*))

    ROOT --> A
    A --> P1
    P1 --> P2
    P1 --> T
    P2 --> P3
    P2 --> L1
    L1 --> E
    L1 --> Y

    style ROOT fill:#e1f5fe
    style P3 fill:#c8e6c9
    style T fill:#c8e6c9
    style E fill:#c8e6c9
    style Y fill:#c8e6c9

Nodes marked with * indicate complete words. Notice how “app”, “apple”, and “apply” share the path “a-p-p”, saving space and enabling fast prefix queries.

Insert Operation Walkthrough

Inserting “apple” into an empty trie:

  flowchart LR
    subgraph Step1["Step 1: Insert 'a'"]
        R1((root)) --> A1((a))
    end

    subgraph Step2["Step 2: Insert 'p'"]
        R2((root)) --> A2((a)) --> P2((p))
    end

    subgraph Step3["Step 3-5: Complete"]
        R3((root)) --> A3((a)) --> P3((p)) --> P4((p)) --> L3((l)) --> E3((e*))
    end

    style E3 fill:#c8e6c9

When to Use This Pattern

Use a Trie when you encounter:

Input involves a dictionary of words or strings
You need to find words with a specific prefix
Problem requires autocomplete or type-ahead suggestions
Need to validate if a word exists in a dictionary
Looking for longest common prefix among strings
IP routing or address lookup problems
Word games like Boggle or crosswords

Core Implementation

The basic trie operations include insert, search, and prefix search:

class TrieNode {
    constructor() {
        this.children = new Map();
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    // Insert a word into the trie
    insert(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children.has(char)) {
                node.children.set(char, new TrieNode());
            }
            node = node.children.get(char);
        }
        node.isEndOfWord = true;
    }

    // Search for exact word match
    search(word) {
        const node = this.getNode(word);
        return node !== null && node.isEndOfWord;
    }

    // Check if any word starts with prefix
    startsWith(prefix) {
        return this.getNode(prefix) !== null;
    }

    // Helper to traverse to node
    getNode(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children.has(char)) {
                return null;
            }
            node = node.children.get(char);
        }
        return node;
    }
}

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: 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

    # Search for exact word match
    def search(self, word: str) -> bool:
        node = self._get_node(word)
        return node is not None and node.is_end_of_word

    # Check if any word starts with prefix
    def starts_with(self, prefix: str) -> bool:
        return self._get_node(prefix) is not None

    # Helper to traverse to node
    def _get_node(self, word: str):
        node = self.root
        for char in word:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Insert a word into the trie
    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEndOfWord = true;
    }

    // Search for exact word match
    public boolean search(String word) {
        TrieNode node = getNode(word);
        return node != null && node.isEndOfWord;
    }

    // Check if any word starts with prefix
    public boolean startsWith(String prefix) {
        return getNode(prefix) != null;
    }

    // Helper to traverse to node
    private TrieNode getNode(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                return null;
            }
            node = node.children.get(ch);
        }
        return node;
    }
}

#include <unordered_map>
#include <string>

class TrieNode {
public:
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;

    TrieNode() : isEndOfWord(false) {}
};

class Trie {
private:
    TrieNode* root;

    // Helper to traverse to node
    TrieNode* getNode(const std::string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() {
        root = new TrieNode();
    }

    // Insert a word into the trie
    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isEndOfWord = true;
    }

    // Search for exact word match
    bool search(const std::string& word) {
        TrieNode* node = getNode(word);
        return node != nullptr && node->isEndOfWord;
    }

    // Check if any word starts with prefix
    bool startsWith(const std::string& prefix) {
        return getNode(prefix) != nullptr;
    }
};

package main

type TrieNode struct {
    children    map[rune]*TrieNode
    isEndOfWord bool
}

func NewTrieNode() *TrieNode {
    return &TrieNode{
        children:    make(map[rune]*TrieNode),
        isEndOfWord: false,
    }
}

type Trie struct {
    root *TrieNode
}

func NewTrie() *Trie {
    return &Trie{root: NewTrieNode()}
}

// Insert a word into the trie
func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = NewTrieNode()
        }
        node = node.children[ch]
    }
    node.isEndOfWord = true
}

// Search for exact word match
func (t *Trie) Search(word string) bool {
    node := t.getNode(word)
    return node != nil && node.isEndOfWord
}

// Check if any word starts with prefix
func (t *Trie) StartsWith(prefix string) bool {
    return t.getNode(prefix) != nil
}

// Helper to traverse to node
func (t *Trie) getNode(word string) *TrieNode {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            return nil
        }
        node = node.children[ch]
    }
    return node
}

class TrieNode
  attr_accessor :children, :is_end_of_word

  def initialize
    @children = {}
    @is_end_of_word = false
  end
end

class Trie
  def initialize
    @root = TrieNode.new
  end

  # Insert a word into the trie
  def insert(word)
    node = @root
    word.each_char do |char|
      node.children[char] ||= TrieNode.new
      node = node.children[char]
    end
    node.is_end_of_word = true
  end

  # Search for exact word match
  def search(word)
    node = get_node(word)
    !node.nil? && node.is_end_of_word
  end

  # Check if any word starts with prefix
  def starts_with(prefix)
    !get_node(prefix).nil?
  end

  private

  # Helper to traverse to node
  def get_node(word)
    node = @root
    word.each_char do |char|
      return nil unless node.children[char]
      node = node.children[char]
    end
    node
  end
end

Complexity Analysis

Operation	Time	Space
Insert	O(M)	O(M)
Search	O(M)	O(1)
StartsWith	O(M)	O(1)
Delete	O(M)	O(M)

Where M is the length of the word or prefix being operated on.

Time Complexity Explained: Each operation traverses at most M characters, visiting one node per character. This is independent of how many words are stored in the trie.

Space Complexity Explained: In the worst case (no shared prefixes), storing N words of average length M requires O(N * M) space. However, with many shared prefixes, space usage is significantly reduced.

Common Mistakes

Forgetting the end-of-word marker: Without marking word endings, you cannot distinguish between stored words and prefixes. For example, if you store “apple”, searching for “app” would incorrectly return true.
Not handling empty strings: Always check for empty input before traversing. An empty string should match the root node for prefix checks.
Memory leaks during deletion: When deleting a word, you must clean up nodes that are no longer part of any word path. Failing to do so wastes memory.
Using wrong data structure for children: Use arrays for fixed small alphabets (like DNA with 4 characters) and hash maps for larger character sets. Wrong choice impacts both speed and memory.

Next Steps

Ready to implement? Check out our Code Templates for reusable implementations with delete operations and advanced features like wildcard matching.

Want to practice? Head to Practice Problems for curated LeetCode problems that apply the trie pattern.

Pro Tip: Tries excel when you need to perform multiple prefix-based operations. For single exact lookups, a hash set is often more efficient. Choose your data structure based on the operations you need most.