Q22: How do you implement a Trie (Prefix Tree) for efficient word insertion and prefix searching?

A Trie is a tree data structure used for fast string prefix lookups. Each node contains a TrieNode[26] child array and a boolean isEndOfWord flag. Operations insert(word), search(word), and startsWith(prefix) run in $O(L)$ time where $L$ is word length.

Trie (Prefix Tree) Implementation

public class Trie {
    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd = false;
    }
    private final TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) curr.children[idx] = new TrieNode();
            curr = curr.children[idx];
        }
        curr.isEnd = true;
    }
    public boolean search(String word) {
        TrieNode node = getNode(word);
        return node != null && node.isEnd;
    }
    public boolean startsWith(String prefix) {
        return getNode(prefix) != null;
    }
    private TrieNode getNode(String str) {
        TrieNode curr = root;
        for (char c : str.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) return null;
            curr = curr.children[idx];
        }
        return curr;
    }
}

💡 Builds prefix paths inside node arrays for $O(L)$ prefix lookups.

Key Takeaways

$O(L)$ insertion and lookup time complexity.
Saves storage by sharing common prefix branch pathways across words.

Knowledge Check

What is the time complexity of searching if a prefix exists in a Trie containing N words of average length L?

Q22: How do you implement a Trie (Prefix Tree) for efficient word insertion and prefix searching?

STAY UPDATED WITH BYTES!