Trie

A trie (prefix tree) is a tree-like data structure for storing strings. Each node represents a character, and paths from root to marked nodes form words.

Node Structure

class TrieNode {
    TrieNode[] children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new TrieNode[26];  // lowercase letters
        isEndOfWord = false;
    }
}

Visual Example

Insert: "apple", "app", "banana"

        (root)
       /      \
      a        b
      |        |
      p        a
     / \\       |
    p   n      n
    |   |      |
    l   a      a
    |   |      |
    e*  a*     n*

* = end of word marker

Trie Class Implementation

class Trie {
    private TrieNode root;

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

    // Insert a word - O(m) where m = word length
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    // Search for exact word - O(m)
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEndOfWord;
    }

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

    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) return null;
            node = node.children[index];
        }
        return node;
    }
}

Delete Operation

public void delete(String word) {
    deleteHelper(root, word, 0);
}

private boolean deleteHelper(TrieNode node, String word, int index) {
    if (index == word.length()) {
        if (!node.isEndOfWord) return false;
        node.isEndOfWord = false;
        return isEmpty(node);  // Can delete this node if no children
    }

    int charIndex = word.charAt(index) - 'a';
    TrieNode child = node.children[charIndex];
    if (child == null) return false;

    boolean shouldDeleteChild = deleteHelper(child, word, index + 1);

    if (shouldDeleteChild) {
        node.children[charIndex] = null;
        return isEmpty(node) && !node.isEndOfWord;
    }
    return false;
}

private boolean isEmpty(TrieNode node) {
    for (TrieNode child : node.children) {
        if (child != null) return false;
    }
    return true;
}

Complexity

Operation	Time	Space
Insert	O(m)	O(m)
Search	O(m)	O(1)
Delete	O(m)	O(1)
startsWith	O(m)	O(1)

where m = length of word/prefix

Space: O(N × m) total where N = number of words, m = avg length. In practice, shared prefixes save space.

Autocomplete / Word Search II

Find all words in trie with given prefix:

public List<String> autocomplete(TrieNode root, String prefix) {
    List<String> results = new ArrayList<>();
    TrieNode node = root;
    for (char c : prefix.toCharArray()) {
        int index = c - 'a';
        if (node.children[index] == null) return results;
        node = node.children[index];
    }
    collectWords(node, prefix, results);
    return results;
}

private void collectWords(TrieNode node, String current, List<String> results) {
    if (node == null) return;
    if (node.isEndOfWord) results.add(current);
    for (int i = 0; i < 26; i++) {
        if (node.children[i] != null) {
            collectWords(node.children[i], current + (char)('a' + i), results);
        }
    }
}

Word Dictionary (Search with Dots)

class WordDictionary {
    TrieNode root;

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

    public void addWord(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        return searchHelper(root, word, 0);
    }

    private boolean searchHelper(TrieNode node, String word, int index) {
        if (node == null) return false;
        if (index == word.length()) return node.isEndOfWord;

        char c = word.charAt(index);
        if (c == '.') {
            for (TrieNode child : node.children) {
                if (searchHelper(child, word, index + 1)) return true;
            }
            return false;
        } else {
            return searchHelper(node.children[c - 'a'], word, index + 1);
        }
    }
}

Longest Common Prefix

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    TrieNode root = new TrieNode();
    for (String s : strs) insert(root, s);

    String prefix = "";
    TrieNode node = root;
    while (hasSingleChild(node)) {
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) {
                prefix += (char)('a' + i);
                node = node.children[i];
                break;
            }
        }
    }
    return prefix;
}

private boolean hasSingleChild(TrieNode node) {
    int count = 0;
    for (TrieNode child : node.children) {
        if (child != null) count++;
    }
    return count == 1 && !node.isEndOfWord;
}

When to Use Trie

• Prefix-based problems: autocomplete, prefix matching
• Word games: Scrabble, Boggle, word search
• String matching: find all words matching pattern
• IP routing: longest prefix match

Trie vs HashMap

Feature	Trie	HashMap
Prefix search	O(m) native	O(n × m)
Space	Shared prefixes	Full strings
Insert/Search	O(m)	O(m) average
Range queries	Efficient	Not supported