Trie / Prefix Tree

1. 1.Implement Trie
   Root node with [26]*TrieNode & isEnd bool; Insert, Search, StartsWith methodsmedium
2. 2.Design Add and Search Words Data Structure
   Trie + DFS: when wildcard "." is encountered, iterate all non-nil childrenmedium
3. 3.Replace Words
   Insert root dictionary words into Trie; walk sentence word until isEnd == truemedium
4. 4.Longest Common Prefix Using Trie
   Insert words into Trie; walk root while node has exactly 1 child & isEnd == falseeasy
5. 5.Search Suggestions System
   Trie + top 3 suggestions cached at each node during insertionmedium
6. 6.Word Search II
   Trie + Grid Backtracking: early prune DFS branch as soon as grid prefix is absent from Triehard
7. 7.Map Sum Pairs
   Trie node storing sum value; Search prefix returns node.Sum directlymedium
8. 8.Longest Word in Dictionary
   Insert all words; BFS/DFS from Trie root considering only nodes with isEnd == truemedium
9. 9.Maximum XOR of Two Numbers in an Array
   Bit Trie (32-bit binary paths): for bit b, prefer opposite child 1-b to maximize XORmedium
10. 10.Stream of Characters
    Reverse Trie: insert words backwards; query checks current character stream in reversehard
11. 11.Prefix and Suffix Search
    Insert combined string suffix + "{" + word into Trie to query in O(L)hard
12. 12.Concatenated Words
    Trie + DP/DFS: test if word can be formed by >= 2 dictionary wordshard
13. 13.Word Break with Trie
    Insert dictionary into Trie; DP[i] checks if substring s[j:i] exists in Triemedium
14. 14.Count Words With Given Prefix
    Walk Trie to prefix node and return node.PrefixCounteasy
15. 15.Implement Autocomplete
    Walk Trie to prefix node + DFS below to collect completionsmedium

1. 16.Short Encoding of Words
   Reverse Trie (Suffix Tree) discarding words that are suffixes of longer wordsmedium
2. 17.Palindrome Pairs
   Trie storing reversed words + checking remaining prefix/suffix for palindromehard
3. 18.Magic Dictionary
   Trie + DFS allowing exactly 1 character mismatchmedium
4. 19.Word Squares
   Trie prefix lookup + Backtracking to construct N x N word matrixhard
5. 20.Design File System
   Trie path hierarchy: split path by "/" and traverse folder nodesmedium
6. 21.Count Distinct Substrings Using Trie
   Insert all suffixes of string into Trie; total distinct substrings = total Trie nodes - 1medium
7. 22.Maximum XOR With an Element From Array
   Offline queries sorted by limit + Bit Trie insertionhard
8. 23.Phone Directory / Contact Search
   Trie storing contact names + returning suggestions for each typed digitmedium
9. 24.IP Routing Prefix Matching
   Binary Trie matching longest subnet mask prefix (e.g. 10.1.4.*/24)medium

How to Think

1. Many words share prefixes?Trie / Prefix Tree
2. Need startsWith(prefix)?Trie
3. Need autocomplete?Trie + DFS from prefix node
4. Need dictionary search while walking a board?Trie + Backtracking (Word Search II)
5. Need maximum XOR?Bit Trie

type TrieNode struct {
    Children [26]*TrieNode
    IsEnd    bool
}

type Trie struct {
    Root *TrieNode
}

func Constructor() Trie {
    return Trie{Root: &TrieNode{}}
}

// 1. Insert: O(L) time
func (t *Trie) Insert(word string) {
    curr := t.Root
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if curr.Children[idx] == nil {
            curr.Children[idx] = &TrieNode{}
        }
        curr = curr.Children[idx]
    }
    curr.IsEnd = true
}

// 2. Search: O(L) time (Path exists AND isEnd == true)
func (t *Trie) Search(word string) bool {
    curr := t.Root
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if curr.Children[idx] == nil {
            return false
        }
        curr = curr.Children[idx]
    }
    return curr.IsEnd
}

// 3. StartsWith: O(L) time (Path exists ONLY)
func (t *Trie) StartsWith(prefix string) bool {
    curr := t.Root
    for i := 0; i < len(prefix); i++ {
        idx := prefix[i] - 'a'
        if curr.Children[idx] == nil {
            return false
        }
        curr = curr.Children[idx]
    }
    return true
}

Search vs StartsWith & Autocomplete

Word Search II & Bit Trie (Max XOR)

Trie            → Character Tree sharing word prefixes
Search          → Character path exists AND isEnd == true
StartsWith      → Character path exists ONLY
Autocomplete    → Walk to prefix node + DFS below
Word Search II  → Trie + Grid Backtracking (Prune dead prefixes!)
Maximum XOR     → Bit Trie preferring opposite bit child (1 - bit)

Common Interview Mistakes

Interview Rules

1. 1. Many words share prefixes / startsWith needed? → Trie / Prefix Tree
2. 2. Search vs StartsWith? → Search = path + isEnd; StartsWith = path only
3. 3. Time Complexity per operation? → O(L) where L is word/prefix length
4. 4. Autocomplete / Search Suggestions? → Walk to prefix node + DFS below
5. 5. Word Search II (Dictionary + Grid)? → Insert dictionary into Trie + Grid Backtracking with prefix pruning
6. 6. Maximum XOR problem? → Bit Trie storing 32-bit binary paths
7. 7. Child Representation? → Fixed a-z uses [26]*TrieNode array; flexible Unicode uses map[rune]*TrieNode
8. 8. Overall Complexity → Time: O(L) | Space: O(N · L)

Trie            → Prefix Tree
Character       → One level
Insert          → Create missing children
Search          → Path + isEnd
Prefix          → Path only
Autocomplete    → Prefix node + DFS
Word Search II  → Trie + Backtracking
Maximum XOR     → Bit Trie
Time            → O(word length)
Main cost       → Memory

💡 Golden Rule: "A Trie turns every prefix into a reusable path, so many words can share the same beginning instead of storing that beginning again and again."