Data Structures & AlgorithmsWord Dictionary & Autocomplete Systems

Word Dictionary & Autocomplete Systems

LevelIntermediate

Duration75 mins

TopicWord Dictionary & Autocomplete Systems

2 / 4

Suggesting All Words with a Prefix

From Prefix to Possibilities

In the previous page, we explored the architecture of autocomplete systems and established why tries are the data structure of choice. Now we confront the core algorithmic challenge: given a prefix typed by the user, how do we efficiently retrieve all words that begin with that prefix?

This operation—prefix-based word suggestion—is the beating heart of any autocomplete system. It must be:

Correct: Return exactly the words that match the prefix
Complete: Find all matching words, not just some of them
Efficient: Execute quickly even when many words match
Flexible: Support various selection and ranking strategies

The solution involves two distinct phases: navigation (finding the prefix node) and collection (gathering all words in the subtree). Each phase has its own complexity characteristics and optimization opportunities.

What You Will Master

By the end of this page, you will understand how to navigate from the root to any prefix node, implement complete subtree collection using DFS, analyze time and space complexity of word collection, handle edge cases robustly, and optimize collection for practical use cases.

The Two-Phase Algorithm

Suggesting all words with a prefix is a two-phase process:

Phase 1: Navigate to the Prefix Node

Starting from the root, follow the path defined by each character in the prefix. If at any point a character's child doesn't exist, the prefix has no matches in the dictionary.

Phase 2: Collect All Words in the Subtree

Once at the prefix node, traverse the entire subtree rooted at that node. Every node marked as an end-of-word represents a complete word starting with our prefix.

Let's trace through an example to build intuition:

Example: Finding all words starting with 'pro'

Consider a trie containing: [program, programmer, programming, progress, project, promise, protect]

       root
         │
         p
         │
         r
         │
         o ← prefix node for 'pro'
        /|
       g j m
       │ │ │
       r e i
       │ │ │
       a c s
       │ │ │
       m t e
      / 
     ∎   m ← 'program', 'programm...'
         |
         e
        /|
       r ∎ ← 'programme'
       |
       ∎ ← 'programmer'

Phase 1: Navigate p → r → o (3 steps) Phase 2: DFS from 'o' node, collecting: program, programmer, programming, progress, project, promise

Note that Phase 1 is O(m) where m is prefix length, independent of dictionary size. Phase 2's cost depends on the number of words that match.

The Prefix Node is the Gateway

Think of the prefix node as a gateway. Everything 'beyond' it (in the subtree) matches the prefix. Everything 'beside' it (sibling branches) doesn't. The trie structure naturally partitions the dictionary based on prefixes, which is exactly why it's perfect for this task.

Phase 1: Navigating to the Prefix Node

The navigation phase is straightforward but deserves careful attention because it's where we detect invalid prefixes early.

The Algorithm:

Start at the root node
For each character c in the prefix:
- If the current node has a child for c, move to that child
- If not, return null (no words match this prefix)
Return the final node (the prefix node)

Key Properties:

Time complexity: O(m) where m is the prefix length
Space complexity: O(1) for the navigation itself
Early termination: Returns immediately if prefix doesn't exist

prefixNavigation.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class TrieNode {
    children: Map<string, TrieNode> = new Map();
    isEndOfWord: boolean = false;
    word: string | null = null;
}
 
/**
 * Navigate to the node representing the given prefix.
 * 
 * @param root - The root node of the trie
 * @param prefix - The prefix to search for
 * @returns The prefix node, or null if prefix doesn't exist
 * 
 * Time Complexity: O(m) where m is prefix length
 * Space Complexity: O(1)
 */
function findPrefixNode(root: TrieNode, prefix: string): TrieNode | null {
    let current = root;
    
    for (const char of prefix) {
        const child = current.children.get(char);
        
        if (!child) {
            // This character doesn't exist at this position
            // No words in the trie start with this prefix
            return null;
        }
        
        current = child;
    }
    
    // We've successfully traversed all prefix characters
    // 'current' is now the prefix node
    return current;
}
 
// Example usage
const trie = buildTrie(['program', 'programmer', 'progress', 'project']);
 
const proNode = findPrefixNode(trie.root, 'pro');
// proNode !== null; all words starting with 'pro' are in this subtree
 
const xyzNode = findPrefixNode(trie.root, 'xyz');
// xyzNode === null; no words start with 'xyz'
 
const emptyNode = findPrefixNode(trie.root, '');
// emptyNode === root; empty prefix matches everything

Edge Cases to Handle:

Empty prefix: Returns the root node. The subtree is the entire trie (all words).
Single character prefix: Works identically; navigates one step from root.
Prefix that is a complete word: The prefix node may itself have isEndOfWord = true. This word should be included in results.
Prefix longer than any word: If the trie contains 'cat' but you search for 'catalog', navigation fails at 'a' (no 'l' child).
Case sensitivity: Decide in advance whether 'A' and 'a' are the same. Typically, normalize to lowercase during both insertion and search.

Normalization Must Be Consistent

Whatever normalization you apply during navigation (lowercase, accent stripping, etc.) must match what you did during insertion. Inconsistent normalization is a common bug that causes 'missing' words that are actually present under different casing.

Phase 2: Collecting Words via DFS

Once we've navigated to the prefix node, we need to collect all words in its subtree. This is a classic tree traversal problem, and Depth-First Search (DFS) is the natural choice.

Why DFS?

Natural for trees: DFS explores one branch completely before moving to the next, which maps well to how tries organize words character by character.
Memory efficient: Only requires stack space proportional to the maximum word length, not the number of words.
Easy to implement: Can be written recursively or iteratively.

The Basic DFS Approach:

Start at the prefix node
If the current node marks end-of-word, add its word to results
Recursively visit all children
Return collected results

dfsCollection.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * Collect all words in a trie subtree using DFS.
 * This version stores the complete word in each end-of-word node.
 * 
 * Time Complexity: O(n) where n is the number of nodes in the subtree
 * Space Complexity: O(h) for recursion stack, where h is max word length
 */
function collectWordsStored(node: TrieNode, results: string[]): void {
    // If this node marks the end of a word, add it to results
    if (node.isEndOfWord && node.word !== null) {
        results.push(node.word);
    }
    
    // Recursively collect from all children
    for (const child of node.children.values()) {
        collectWordsStored(child, results);
    }
}
 
/**
 * Alternative: Build words character by character during traversal.
 * Useful when words aren't stored in nodes.
 * 
 * Time Complexity: O(n) for traversal + O(total_chars) for string building
 * Space Complexity: O(h) for recursion + O(h) for current path
 */
function collectWordsBuild(
    node: TrieNode, 
    currentPath: string, 
    results: string[]
): void {
    if (node.isEndOfWord) {
        results.push(currentPath);
    }
    
    for (const [char, child] of node.children.entries()) {
        collectWordsBuild(child, currentPath + char, results);
    }
}
 
/**
 * Main function: Get all words starting with a prefix
 */
function getAllWordsWithPrefix(root: TrieNode, prefix: string): string[] {
    const prefixNode = findPrefixNode(root, prefix);
    
    if (prefixNode === null) {
        return [];  // No words match this prefix
    }
    
    const results: string[] = [];
    
    // Option 1: If words are stored in nodes
    collectWordsStored(prefixNode, results);
    
    // Option 2: If building words during traversal
    // collectWordsBuild(prefixNode, prefix, results);
    
    return results;
}

Stored vs Built Words:

There are two common approaches for retrieving the actual word strings:

Approach	Pros	Cons
Store word in node	Fast retrieval (O(1) per word)	Higher memory usage
Build during traversal	Lower memory	String concatenation overhead

For autocomplete, storing words in nodes is usually preferred because:

We need the actual strings for display
The memory cost is acceptable for most use cases
It simplifies the code

Iterative DFS Alternative

Recursion can cause stack overflow for very deep tries (words with thousands of characters). An iterative approach using an explicit stack avoids this. The logic is identical: push the root, pop nodes one by one, process them, push their children. This is rarely needed for natural language but essential for applications like long DNA sequences.

Time and Space Complexity Analysis

Understanding the complexity of prefix-based word retrieval is crucial for predicting system behavior and making informed design decisions.

Let's define our variables:

m = length of the prefix
n = number of nodes in the entire trie
k = number of words matching the prefix
s = number of nodes in the subtree rooted at the prefix node
L = maximum word length

Complexity Analysis of Prefix Word Retrieval
Operation	Time Complexity	Space Complexity	Notes
Navigate to prefix	O(m)	O(1)	m = prefix length, independent of dictionary size
Collect all words (DFS)	O(s)	O(L)	s = subtree size; L = max depth for recursion stack
Total for getAllWordsWithPrefix	O(m + s)	O(L + k)	k words in result array

Detailed Breakdown:

Navigation: O(m) We traverse exactly m edges in the trie, one per character in the prefix. This is independent of the dictionary size. Whether your dictionary has 1,000 or 1,000,000 words, navigating to 'prog' takes 4 steps.

Collection: O(s) We visit every node in the subtree rooted at the prefix node. Each node is visited exactly once. The number of nodes s depends on:

How many words share this prefix
How much those words differ after the prefix

Space for Recursion: O(L) The recursion depth is at most the length of the longest word in the subtree. For natural language, this is typically 20-30 characters. For other applications (URLs, file paths), it could be much longer.

Space for Results: O(k × average_word_length) We store k words, each requiring space proportional to its length. If words are stored in nodes, this is just O(k) for the array of references.

The Short Prefix Problem

Short prefixes match many words. If your dictionary has 500,000 words and 30% start with 's', searching for prefix 's' means navigating 1 step (fast!) then collecting 150,000 words (slow!). This is why autocomplete systems don't fetch all matches—they limit results and use ranking instead.

Worst Case Analysis:

The worst case for collection occurs when:

The prefix is very short (or empty)
Many words share that prefix
Words are long and diverse

Example: prefix '' (empty) on an English dictionary:

Navigation: O(1) — we're already at root
Collection: O(n) — we traverse every node in the entire trie
Results: O(total characters in all words)

This is essentially "return the entire dictionary," which is never what users want but highlights why we need limits.

Best Case Analysis:

The best case occurs when:

The prefix doesn't exist in the trie
Collection never happens

Time: O(m) for navigation, O(1) for empty result.

Practical Average Case:

For a well-distributed dictionary with typical autocomplete usage:

Users type 3-6 characters before expecting results
At this prefix length, typically 10-1000 words match
Collection is fast (milliseconds for thousands of nodes)
Ranking and limiting dominate if applied

Iterative DFS Implementation

While recursive DFS is elegant, an iterative version using an explicit stack is sometimes necessary. This avoids potential stack overflow for deep tries and gives you more control over the traversal.

When to Use Iterative:

Words can be extremely long (thousands of characters)
You need to pause and resume collection
You want to limit collection by count or time
You're in a language/environment with limited call stack

iterativeDFS.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**
 * Collect words using iterative DFS with explicit stack.
 * More control, no recursion depth limits.
 * 
 * Time Complexity: O(s) where s is subtree size
 * Space Complexity: O(w) where w is max width at any level (stack size)
 */
function collectWordsIterative(prefixNode: TrieNode): string[] {
    const results: string[] = [];
    const stack: TrieNode[] = [prefixNode];
    
    while (stack.length > 0) {
        const current = stack.pop()!;
        
        // Process current node
        if (current.isEndOfWord && current.word !== null) {
            results.push(current.word);
        }
        
        // Add children to stack
        // Note: Order of traversal depends on iteration order of children
        for (const child of current.children.values()) {
            stack.push(child);
        }
    }
    
    return results;
}
 
/**
 * Collect with a maximum count limit.
 * Stops early once we have enough results.
 * 
 * Useful for autocomplete where we only need top-K results.
 */
function collectWordsWithLimit(prefixNode: TrieNode, limit: number): string[] {
    const results: string[] = [];
    const stack: TrieNode[] = [prefixNode];
    
    while (stack.length > 0 && results.length < limit) {
        const current = stack.pop()!;
        
        if (current.isEndOfWord && current.word !== null) {
            results.push(current.word);
            
            if (results.length >= limit) {
                break;  // Early termination
            }
        }
        
        for (const child of current.children.values()) {
            stack.push(child);
        }
    }
    
    return results;
}
 
/**
 * Collect with time limit (for responsive systems).
 * Ensures we don't block too long on large subtrees.
 */
function collectWordsWithTimeout(
    prefixNode: TrieNode, 
    maxTimeMs: number
): string[] {
    const results: string[] = [];
    const stack: TrieNode[] = [prefixNode];
    const startTime = performance.now();
    
    while (stack.length > 0) {
        // Check timeout periodically (every 100 nodes)
        if (results.length % 100 === 0) {
            if (performance.now() - startTime > maxTimeMs) {
                console.warn('Collection timeout - returning partial results');
                break;
            }
        }
        
        const current = stack.pop()!;
        
        if (current.isEndOfWord && current.word !== null) {
            results.push(current.word);
        }
        
        for (const child of current.children.values()) {
            stack.push(child);
        }
    }
    
    return results;
}

BFS Alternative

Using a queue instead of a stack gives Breadth-First Search. BFS explores nodes level by level, which means shorter words are found before longer ones. This can be useful if you want to prioritize shorter completions. Simply replace stack.pop() with queue.shift() (or use a proper deque for O(1) operations).

Handling Common Edge Cases

Robust autocomplete implementations must handle various edge cases gracefully. Let's examine each one in detail.

Edge Case 1: Empty Prefix

When the user hasn't typed anything yet, the prefix is empty. This should return all words in the dictionary (or trigger a different behavior like showing recent searches).

edgeCases.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Handle empty prefix case.
 * Empty prefix = start from root, all words match.
 */
function getWordsWithPrefix(root: TrieNode, prefix: string): string[] {
    if (prefix === '') {
        // Decision point: return all words or handle specially?
        // Option 1: Return all (could be slow for large dictionaries)
        const results: string[] = [];
        collectWordsStored(root, results);
        return results;
        
        // Option 2: Return empty (let caller show recent/popular)
        // return [];
        
        // Option 3: Return most popular N words
        // return getMostPopular(root, 10);
    }
    
    const prefixNode = findPrefixNode(root, prefix);
    if (!prefixNode) return [];
    
    const results: string[] = [];
    collectWordsStored(prefixNode, results);
    return results;
}
 
/**
 * Edge Case 2: Prefix that is itself a complete word.
 * Example: prefix "program" when "program" is a word.
 * The prefix node should be included if it marks end-of-word.
 */
function prefixIsWord(root: TrieNode, prefix: string): boolean {
    const prefixNode = findPrefixNode(root, prefix);
    return prefixNode !== null && prefixNode.isEndOfWord;
}
// This is automatically handled if collectWords checks isEndOfWord
 
/**
 * Edge Case 3: Non-existent prefix.
 * findPrefixNode returns null, we return empty array.
 */
function handleNonExistentPrefix(): void {
    const words = getWordsWithPrefix(trieRoot, 'xyz');
    console.log(words);  // [] - empty, not an error
}
 
/**
 * Edge Case 4: Special characters and mixed case.
 * Normalize consistently in both insert and search.
 */
function normalizeQuery(query: string): string {
    return query
        .toLowerCase()                    // Case insensitive
        .normalize('NFD')                 // Decompose accented characters
        .replace(/[̀-ͯ]/g, '') // Remove diacritics
        .replace(/[^a-z0-9]/g, '');      // Remove special chars (optional)
}
 
/**
 * Edge Case 5: Unicode and emoji.
 * Ensure character iteration handles multi-byte correctly.
 */
function iterateCharacters(str: string): string[] {
    // Using spread operator handles Unicode surrogates correctly
    return [...str];
}
// "café" → ['c', 'a', 'f', 'é']
// "🎉hello" → ['🎉', 'h', 'e', 'l', 'l', 'o']

Complete Edge Case Checklist

•Empty prefix — Decide on behavior: all words, empty result, or curated suggestions
•Prefix is a complete word — Include it in results if marked as end-of-word
•Non-existent prefix — Return empty array, not null or error
•Single character prefix — Works normally; may have many matches
•Prefix longer than longest word — Navigation fails; return empty
•Case variations — Normalize during insert AND search consistently
•Accented characters — Use Unicode normalization (NFD/NFC)
•Special characters — Decide whether to strip or include
•Whitespace — Leading/trailing spaces, multiple spaces
•Unicode/Emoji — Proper character iteration (use spread operator or grapheme segmentation)

Defensive Programming

Always validate input at the API boundary. A production autocomplete endpoint should handle null, undefined, extremely long strings, and malformed input gracefully—returning empty results rather than throwing errors.

Ordered Collection: Alphabetical Results

Sometimes you want results in a specific order—typically alphabetical. The trie structure can produce alphabetically sorted results naturally, with slight modifications to the traversal.

Key Insight:

A trie already organizes words by their prefixes. If we traverse children in alphabetical order, we visit nodes in a way that produces words in alphabetical order.

Requirements for Alphabetical Collection:

Children must be stored in a sorted structure (sorted map or array)
Traversal must visit children in sorted key order
For hash-based children, sort keys before iterating

orderedCollection.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class SortedTrieNode {
    // Using a sorted array of [char, node] pairs for ordered iteration
    children: [string, SortedTrieNode][] = [];
    isEndOfWord: boolean = false;
    word: string | null = null;
    
    getChild(char: string): SortedTrieNode | undefined {
        // Binary search for O(log k) lookup
        let left = 0, right = this.children.length - 1;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (this.children[mid][0] === char) {
                return this.children[mid][1];
            } else if (this.children[mid][0] < char) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return undefined;
    }
    
    addChild(char: string, node: SortedTrieNode): void {
        // Insert in sorted position
        let i = 0;
        while (i < this.children.length && this.children[i][0] < char) {
            i++;
        }
        this.children.splice(i, 0, [char, node]);
    }
}
 
/**
 * Collect words in alphabetical order.
 * Children are traversed in sorted order, producing sorted results.
 */
function collectWordsAlphabetical(
    node: SortedTrieNode, 
    results: string[]
): void {
    // Pre-order: add word first, then explore children
    if (node.isEndOfWord && node.word !== null) {
        results.push(node.word);
    }
    
    // Children are already sorted, iterate in order
    for (const [char, child] of node.children) {
        collectWordsAlphabetical(child, results);
    }
}
 
// Alternative: Sort after collection (simpler but less efficient)
function collectThenSort(prefixNode: TrieNode): string[] {
    const results: string[] = [];
    collectWordsStored(prefixNode, results);
    return results.sort((a, b) => a.localeCompare(b));
}

Trade-offs:

Approach	Insert Time	Lookup Time	Collection Order	Use Case
Hash Map children	O(1)	O(1)	Unordered	Maximum speed, sort later
Sorted Array children	O(k)	O(log k)	Alphabetical	Always need sorted output
TreeMap children	O(log k)	O(log k)	Alphabetical	Balanced performance

where k is the number of children (alphabet size, typically 26-256).

For autocomplete, hash-based children with post-collection sorting is usually best because:

Insert and lookup are the dominant operations
Ranking typically overrides alphabetical order anyway
Sorting k results is trivial when k is small (5-10 suggestions)

Lexicographic Order in Unicode

For non-ASCII text, 'alphabetical' order depends on locale. 'ñ' comes after 'n' in Spanish but after 'z' in English sorting. Use locale-aware comparison like Intl.Collator in JavaScript or locale.strxfrm() in Python for proper international sorting.

Limiting Results Efficiently

In practice, autocomplete shows only 5-10 suggestions. Collecting thousands of matches just to discard most of them is wasteful. Let's explore strategies for efficient result limiting.

Strategy 1: Early Termination

The simplest approach—stop collecting once you have enough results. Works well when you don't need ranking.

Strategy 2: Priority-Based Collection

If nodes store ranking information (popularity, recency), traverse in a way that finds the best results first.

Strategy 3: Bounded Heap

Use a min-heap of size K. As you traverse, add words to the heap. When full, only add if the new word is better than the worst in the heap.

limitedCollection.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import { MinHeap } from './heap';  // Assume we have a min-heap
 
interface RankedWord {
    word: string;
    score: number;
}
 
/**
 * Strategy 3: Bounded heap for top-K collection.
 * Efficiently finds the K highest-scored words without
 * collecting all words first.
 * 
 * Time: O(s log K) where s is subtree size
 * Space: O(K) for the heap
 */
function collectTopK(prefixNode: TrieNode, k: number): string[] {
    // Min-heap keeps track of top K (smallest of the top K at root)
    const minHeap = new MinHeap<RankedWord>(
        (a, b) => a.score - b.score  // Compare by score
    );
    
    const stack: TrieNode[] = [prefixNode];
    
    while (stack.length > 0) {
        const current = stack.pop()!;
        
        if (current.isEndOfWord && current.word !== null) {
            const candidate: RankedWord = {
                word: current.word,
                score: current.frequency  // Assume nodes store frequency
            };
            
            if (minHeap.size() < k) {
                // Haven't found k words yet, add unconditionally
                minHeap.push(candidate);
            } else if (candidate.score > minHeap.peek()!.score) {
                // This word is better than the worst in our top-K
                minHeap.pop();  // Remove worst
                minHeap.push(candidate);  // Add better one
            }
            // If score <= worst in heap, skip this word
        }
        
        for (const child of current.children.values()) {
            stack.push(child);
        }
    }
    
    // Extract results (will be in heap order, reverse for descending)
    const results: string[] = [];
    while (minHeap.size() > 0) {
        results.push(minHeap.pop()!.word);
    }
    
    return results.reverse();  // Best first
}
 
/**
 * Optimization: Branch pruning with max-score metadata.
 * If nodes store the maximum score of any descendant,
 * we can skip entire branches that can't compete.
 */
interface TrieNodeWithMaxScore extends TrieNode {
    maxDescendantScore: number;  // Max score in this subtree
}
 
function collectTopKOptimized(
    prefixNode: TrieNodeWithMaxScore, 
    k: number
): string[] {
    const minHeap = new MinHeap<RankedWord>(
        (a, b) => a.score - b.score
    );
    
    // Use priority queue for traversal - visit high-potential branches first
    const pq = new MaxHeap<TrieNodeWithMaxScore>(
        (a, b) => a.maxDescendantScore - b.maxDescendantScore
    );
    pq.push(prefixNode);
    
    while (pq.size() > 0) {
        const current = pq.pop()!;
        
        // Pruning: if this branch can't beat our worst top-K, skip it
        if (minHeap.size() >= k && 
            current.maxDescendantScore <= minHeap.peek()!.score) {
            continue;  // Skip entire branch
        }
        
        if (current.isEndOfWord && current.word !== null) {
            const candidate: RankedWord = {
                word: current.word,
                score: current.frequency
            };
            
            if (minHeap.size() < k) {
                minHeap.push(candidate);
            } else if (candidate.score > minHeap.peek()!.score) {
                minHeap.pop();
                minHeap.push(candidate);
            }
        }
        
        for (const child of current.children.values()) {
            pq.push(child as TrieNodeWithMaxScore);
        }
    }
    
    const results: string[] = [];
    while (minHeap.size() > 0) {
        results.push(minHeap.pop()!.word);
    }
    return results.reverse();
}

Comparison of Result Limiting Strategies
Strategy	Time Complexity	Quality	Implementation
Early termination	O(m + number_found)	Low (arbitrary results)	Simple
Collect all + sort + slice	O(m + s + s log s)	High (truly top-K)	Simple
Bounded heap (basic)	O(m + s log K)	High (truly top-K)	Medium
Bounded heap + pruning	O(m + visited log K)	High (truly top-K)	Complex

When Is Pruning Worth It?

Branch pruning with max-score metadata requires maintaining this metadata during insertion (additional work). It pays off when: the subtree is large, score distribution is skewed (few high-score branches), and queries frequently hit common prefixes. For small datasets, the overhead isn't worth it.

Summary: Mastering Prefix Word Collection

We've thoroughly explored how to suggest all words with a given prefix—the fundamental operation behind autocomplete. Let's consolidate what we've learned:

Key Takeaways

•Two-phase algorithm — Navigate to the prefix node in O(m), then collect all words in the subtree in O(s). Total: O(m + s).
•DFS is the natural choice — Recursive DFS is clean and simple; iterative DFS handles deep tries and enables early termination.
•Complexity depends on the subtree — Short prefixes match many words, making collection expensive. Limit results in practice.
•Edge cases matter — Empty prefix, non-existent prefix, prefix-is-word, case sensitivity, and Unicode all need handling.
•Alphabetical order is achievable — Use sorted children structures or sort after collection.
•Top-K requires smarter collection — Bounded heaps, branch pruning, and priority-guided traversal find the best results efficiently.
•Early termination saves work — Don't collect 10,000 words to show 5 suggestions.

What's Next:

In the next page, we'll dive deeper into DFS from prefix node—specifically, the detailed mechanics of traversing trie subtrees. We'll explore different traversal orders, how to construct words during traversal, and advanced patterns for combining collection with filtering.

Page Complete

You now understand how to implement prefix-based word suggestion completely—from navigating to the prefix node through collecting all matching words. You can analyze the complexity, handle edge cases, and apply various limiting strategies. This knowledge forms the core of any autocomplete implementation.

2 / 4

Loading learning content...

Data Structures & AlgorithmsWord Dictionary & Autocomplete Systems

Word Dictionary & Autocomplete Systems

LevelIntermediate

Duration75 mins

TopicWord Dictionary & Autocomplete Systems

2 / 4

Suggesting All Words with a Prefix

From Prefix to Possibilities

This operation—prefix-based word suggestion—is the beating heart of any autocomplete system. It must be:

Correct: Return exactly the words that match the prefix
Complete: Find all matching words, not just some of them
Efficient: Execute quickly even when many words match
Flexible: Support various selection and ranking strategies

What You Will Master

The Two-Phase Algorithm

Suggesting all words with a prefix is a two-phase process:

Phase 1: Navigate to the Prefix Node

Starting from the root, follow the path defined by each character in the prefix. If at any point a character's child doesn't exist, the prefix has no matches in the dictionary.

Phase 2: Collect All Words in the Subtree

Once at the prefix node, traverse the entire subtree rooted at that node. Every node marked as an end-of-word represents a complete word starting with our prefix.

Let's trace through an example to build intuition:

Example: Finding all words starting with 'pro'

Consider a trie containing: [program, programmer, programming, progress, project, promise, protect]

       root
         │
         p
         │
         r
         │
         o ← prefix node for 'pro'
        /|
       g j m
       │ │ │
       r e i
       │ │ │
       a c s
       │ │ │
       m t e
      / 
     ∎   m ← 'program', 'programm...'
         |
         e
        /|
       r ∎ ← 'programme'
       |
       ∎ ← 'programmer'

Phase 1: Navigate p → r → o (3 steps) Phase 2: DFS from 'o' node, collecting: program, programmer, programming, progress, project, promise

Note that Phase 1 is O(m) where m is prefix length, independent of dictionary size. Phase 2's cost depends on the number of words that match.

The Prefix Node is the Gateway

Phase 1: Navigating to the Prefix Node

The navigation phase is straightforward but deserves careful attention because it's where we detect invalid prefixes early.

The Algorithm:

Start at the root node
For each character c in the prefix:
- If the current node has a child for c, move to that child
- If not, return null (no words match this prefix)
Return the final node (the prefix node)

Key Properties:

Time complexity: O(m) where m is the prefix length
Space complexity: O(1) for the navigation itself
Early termination: Returns immediately if prefix doesn't exist

prefixNavigation.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class TrieNode {
    children: Map<string, TrieNode> = new Map();
    isEndOfWord: boolean = false;
    word: string | null = null;
}
 
/**
 * Navigate to the node representing the given prefix.
 * 
 * @param root - The root node of the trie
 * @param prefix - The prefix to search for
 * @returns The prefix node, or null if prefix doesn't exist
 * 
 * Time Complexity: O(m) where m is prefix length
 * Space Complexity: O(1)
 */
function findPrefixNode(root: TrieNode, prefix: string): TrieNode | null {
    let current = root;
    
    for (const char of prefix) {
        const child = current.children.get(char);
        
        if (!child) {
            // This character doesn't exist at this position
            // No words in the trie start with this prefix
            return null;
        }
        
        current = child;
    }
    
    // We've successfully traversed all prefix characters
    // 'current' is now the prefix node
    return current;
}
 
// Example usage
const trie = buildTrie(['program', 'programmer', 'progress', 'project']);
 
const proNode = findPrefixNode(trie.root, 'pro');
// proNode !== null; all words starting with 'pro' are in this subtree
 
const xyzNode = findPrefixNode(trie.root, 'xyz');
// xyzNode === null; no words start with 'xyz'
 
const emptyNode = findPrefixNode(trie.root, '');
// emptyNode === root; empty prefix matches everything

Edge Cases to Handle:

Empty prefix: Returns the root node. The subtree is the entire trie (all words).
Single character prefix: Works identically; navigates one step from root.
Prefix that is a complete word: The prefix node may itself have isEndOfWord = true. This word should be included in results.
Prefix longer than any word: If the trie contains 'cat' but you search for 'catalog', navigation fails at 'a' (no 'l' child).
Case sensitivity: Decide in advance whether 'A' and 'a' are the same. Typically, normalize to lowercase during both insertion and search.

Normalization Must Be Consistent

Phase 2: Collecting Words via DFS

Once we've navigated to the prefix node, we need to collect all words in its subtree. This is a classic tree traversal problem, and Depth-First Search (DFS) is the natural choice.

Why DFS?

Natural for trees: DFS explores one branch completely before moving to the next, which maps well to how tries organize words character by character.
Memory efficient: Only requires stack space proportional to the maximum word length, not the number of words.
Easy to implement: Can be written recursively or iteratively.

The Basic DFS Approach:

Start at the prefix node
If the current node marks end-of-word, add its word to results
Recursively visit all children
Return collected results

dfsCollection.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * Collect all words in a trie subtree using DFS.
 * This version stores the complete word in each end-of-word node.
 * 
 * Time Complexity: O(n) where n is the number of nodes in the subtree
 * Space Complexity: O(h) for recursion stack, where h is max word length
 */
function collectWordsStored(node: TrieNode, results: string[]): void {
    // If this node marks the end of a word, add it to results
    if (node.isEndOfWord && node.word !== null) {
        results.push(node.word);
    }
    
    // Recursively collect from all children
    for (const child of node.children.values()) {
        collectWordsStored(child, results);
    }
}
 
/**
 * Alternative: Build words character by character during traversal.
 * Useful when words aren't stored in nodes.
 * 
 * Time Complexity: O(n) for traversal + O(total_chars) for string building
 * Space Complexity: O(h) for recursion + O(h) for current path
 */
function collectWordsBuild(
    node: TrieNode, 
    currentPath: string, 
    results: string[]
): void {
    if (node.isEndOfWord) {
        results.push(currentPath);
    }
    
    for (const [char, child] of node.children.entries()) {
        collectWordsBuild(child, currentPath + char, results);
    }
}
 
/**
 * Main function: Get all words starting with a prefix
 */
function getAllWordsWithPrefix(root: TrieNode, prefix: string): string[] {
    const prefixNode = findPrefixNode(root, prefix);
    
    if (prefixNode === null) {
        return [];  // No words match this prefix
    }
    
    const results: string[] = [];
    
    // Option 1: If words are stored in nodes
    collectWordsStored(prefixNode, results);
    
    // Option 2: If building words during traversal
    // collectWordsBuild(prefixNode, prefix, results);
    
    return results;
}

Stored vs Built Words:

There are two common approaches for retrieving the actual word strings:

Approach	Pros	Cons
Store word in node	Fast retrieval (O(1) per word)	Higher memory usage
Build during traversal	Lower memory	String concatenation overhead

For autocomplete, storing words in nodes is usually preferred because:

We need the actual strings for display
The memory cost is acceptable for most use cases
It simplifies the code

Iterative DFS Alternative

Time and Space Complexity Analysis

Understanding the complexity of prefix-based word retrieval is crucial for predicting system behavior and making informed design decisions.

Let's define our variables:

m = length of the prefix
n = number of nodes in the entire trie
k = number of words matching the prefix
s = number of nodes in the subtree rooted at the prefix node
L = maximum word length

Complexity Analysis of Prefix Word Retrieval
Operation	Time Complexity	Space Complexity	Notes
Navigate to prefix	O(m)	O(1)	m = prefix length, independent of dictionary size
Collect all words (DFS)	O(s)	O(L)	s = subtree size; L = max depth for recursion stack
Total for getAllWordsWithPrefix	O(m + s)	O(L + k)	k words in result array

Detailed Breakdown:

Collection: O(s) We visit every node in the subtree rooted at the prefix node. Each node is visited exactly once. The number of nodes s depends on:

How many words share this prefix
How much those words differ after the prefix

Space for Results: O(k × average_word_length) We store k words, each requiring space proportional to its length. If words are stored in nodes, this is just O(k) for the array of references.

The Short Prefix Problem

Worst Case Analysis:

The worst case for collection occurs when:

The prefix is very short (or empty)
Many words share that prefix
Words are long and diverse

Example: prefix '' (empty) on an English dictionary:

Navigation: O(1) — we're already at root
Collection: O(n) — we traverse every node in the entire trie
Results: O(total characters in all words)

This is essentially "return the entire dictionary," which is never what users want but highlights why we need limits.

Best Case Analysis:

The best case occurs when:

The prefix doesn't exist in the trie
Collection never happens

Time: O(m) for navigation, O(1) for empty result.

Practical Average Case:

For a well-distributed dictionary with typical autocomplete usage:

Users type 3-6 characters before expecting results
At this prefix length, typically 10-1000 words match
Collection is fast (milliseconds for thousands of nodes)
Ranking and limiting dominate if applied

Iterative DFS Implementation

While recursive DFS is elegant, an iterative version using an explicit stack is sometimes necessary. This avoids potential stack overflow for deep tries and gives you more control over the traversal.

When to Use Iterative:

Words can be extremely long (thousands of characters)
You need to pause and resume collection
You want to limit collection by count or time
You're in a language/environment with limited call stack

iterativeDFS.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**
 * Collect words using iterative DFS with explicit stack.
 * More control, no recursion depth limits.
 * 
 * Time Complexity: O(s) where s is subtree size
 * Space Complexity: O(w) where w is max width at any level (stack size)
 */
function collectWordsIterative(prefixNode: TrieNode): string[] {
    const results: string[] = [];
    const stack: TrieNode[] = [prefixNode];
    
    while (stack.length > 0) {
        const current = stack.pop()!;
        
        // Process current node
        if (current.isEndOfWord && current.word !== null) {
            results.push(current.word);
        }
        
        // Add children to stack
        // Note: Order of traversal depends on iteration order of children
        for (const child of current.children.values()) {
            stack.push(child);
        }
    }
    
    return results;
}
 
/**
 * Collect with a maximum count limit.
 * Stops early once we have enough results.
 * 
 * Useful for autocomplete where we only need top-K results.
 */
function collectWordsWithLimit(prefixNode: TrieNode, limit: number): string[] {
    const results: string[] = [];
    const stack: TrieNode[] = [prefixNode];
    
    while (stack.length > 0 && results.length < limit) {
        const current = stack.pop()!;
        
        if (current.isEndOfWord && current.word !== null) {
            results.push(current.word);
            
            if (results.length >= limit) {
                break;  // Early termination
            }
        }
        
        for (const child of current.children.values()) {
            stack.push(child);
        }
    }
    
    return results;
}
 
/**
 * Collect with time limit (for responsive systems).
 * Ensures we don't block too long on large subtrees.
 */
function collectWordsWithTimeout(
    prefixNode: TrieNode, 
    maxTimeMs: number
): string[] {
    const results: string[] = [];
    const stack: TrieNode[] = [prefixNode];
    const startTime = performance.now();
    
    while (stack.length > 0) {
        // Check timeout periodically (every 100 nodes)
        if (results.length % 100 === 0) {
            if (performance.now() - startTime > maxTimeMs) {
                console.warn('Collection timeout - returning partial results');
                break;
            }
        }
        
        const current = stack.pop()!;
        
        if (current.isEndOfWord && current.word !== null) {
            results.push(current.word);
        }
        
        for (const child of current.children.values()) {
            stack.push(child);
        }
    }
    
    return results;
}

BFS Alternative

Handling Common Edge Cases

Robust autocomplete implementations must handle various edge cases gracefully. Let's examine each one in detail.

Edge Case 1: Empty Prefix

When the user hasn't typed anything yet, the prefix is empty. This should return all words in the dictionary (or trigger a different behavior like showing recent searches).

edgeCases.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Handle empty prefix case.
 * Empty prefix = start from root, all words match.
 */
function getWordsWithPrefix(root: TrieNode, prefix: string): string[] {
    if (prefix === '') {
        // Decision point: return all words or handle specially?
        // Option 1: Return all (could be slow for large dictionaries)
        const results: string[] = [];
        collectWordsStored(root, results);
        return results;
        
        // Option 2: Return empty (let caller show recent/popular)
        // return [];
        
        // Option 3: Return most popular N words
        // return getMostPopular(root, 10);
    }
    
    const prefixNode = findPrefixNode(root, prefix);
    if (!prefixNode) return [];
    
    const results: string[] = [];
    collectWordsStored(prefixNode, results);
    return results;
}
 
/**
 * Edge Case 2: Prefix that is itself a complete word.
 * Example: prefix "program" when "program" is a word.
 * The prefix node should be included if it marks end-of-word.
 */
function prefixIsWord(root: TrieNode, prefix: string): boolean {
    const prefixNode = findPrefixNode(root, prefix);
    return prefixNode !== null && prefixNode.isEndOfWord;
}
// This is automatically handled if collectWords checks isEndOfWord
 
/**
 * Edge Case 3: Non-existent prefix.
 * findPrefixNode returns null, we return empty array.
 */
function handleNonExistentPrefix(): void {
    const words = getWordsWithPrefix(trieRoot, 'xyz');
    console.log(words);  // [] - empty, not an error
}
 
/**
 * Edge Case 4: Special characters and mixed case.
 * Normalize consistently in both insert and search.
 */
function normalizeQuery(query: string): string {
    return query
        .toLowerCase()                    // Case insensitive
        .normalize('NFD')                 // Decompose accented characters
        .replace(/[̀-ͯ]/g, '') // Remove diacritics
        .replace(/[^a-z0-9]/g, '');      // Remove special chars (optional)
}
 
/**
 * Edge Case 5: Unicode and emoji.
 * Ensure character iteration handles multi-byte correctly.
 */
function iterateCharacters(str: string): string[] {
    // Using spread operator handles Unicode surrogates correctly
    return [...str];
}
// "café" → ['c', 'a', 'f', 'é']
// "🎉hello" → ['🎉', 'h', 'e', 'l', 'l', 'o']

Complete Edge Case Checklist

•Empty prefix — Decide on behavior: all words, empty result, or curated suggestions
•Prefix is a complete word — Include it in results if marked as end-of-word
•Non-existent prefix — Return empty array, not null or error
•Single character prefix — Works normally; may have many matches
•Prefix longer than longest word — Navigation fails; return empty
•Case variations — Normalize during insert AND search consistently
•Accented characters — Use Unicode normalization (NFD/NFC)
•Special characters — Decide whether to strip or include
•Whitespace — Leading/trailing spaces, multiple spaces
•Unicode/Emoji — Proper character iteration (use spread operator or grapheme segmentation)

Defensive Programming

Ordered Collection: Alphabetical Results

Sometimes you want results in a specific order—typically alphabetical. The trie structure can produce alphabetically sorted results naturally, with slight modifications to the traversal.

Key Insight:

A trie already organizes words by their prefixes. If we traverse children in alphabetical order, we visit nodes in a way that produces words in alphabetical order.

Requirements for Alphabetical Collection:

Children must be stored in a sorted structure (sorted map or array)
Traversal must visit children in sorted key order
For hash-based children, sort keys before iterating

orderedCollection.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class SortedTrieNode {
    // Using a sorted array of [char, node] pairs for ordered iteration
    children: [string, SortedTrieNode][] = [];
    isEndOfWord: boolean = false;
    word: string | null = null;
    
    getChild(char: string): SortedTrieNode | undefined {
        // Binary search for O(log k) lookup
        let left = 0, right = this.children.length - 1;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (this.children[mid][0] === char) {
                return this.children[mid][1];
            } else if (this.children[mid][0] < char) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return undefined;
    }
    
    addChild(char: string, node: SortedTrieNode): void {
        // Insert in sorted position
        let i = 0;
        while (i < this.children.length && this.children[i][0] < char) {
            i++;
        }
        this.children.splice(i, 0, [char, node]);
    }
}
 
/**
 * Collect words in alphabetical order.
 * Children are traversed in sorted order, producing sorted results.
 */
function collectWordsAlphabetical(
    node: SortedTrieNode, 
    results: string[]
): void {
    // Pre-order: add word first, then explore children
    if (node.isEndOfWord && node.word !== null) {
        results.push(node.word);
    }
    
    // Children are already sorted, iterate in order
    for (const [char, child] of node.children) {
        collectWordsAlphabetical(child, results);
    }
}
 
// Alternative: Sort after collection (simpler but less efficient)
function collectThenSort(prefixNode: TrieNode): string[] {
    const results: string[] = [];
    collectWordsStored(prefixNode, results);
    return results.sort((a, b) => a.localeCompare(b));
}

Trade-offs:

Approach	Insert Time	Lookup Time	Collection Order	Use Case
Hash Map children	O(1)	O(1)	Unordered	Maximum speed, sort later
Sorted Array children	O(k)	O(log k)	Alphabetical	Always need sorted output
TreeMap children	O(log k)	O(log k)	Alphabetical	Balanced performance

where k is the number of children (alphabet size, typically 26-256).

For autocomplete, hash-based children with post-collection sorting is usually best because:

Insert and lookup are the dominant operations
Ranking typically overrides alphabetical order anyway
Sorting k results is trivial when k is small (5-10 suggestions)

Lexicographic Order in Unicode

Limiting Results Efficiently

In practice, autocomplete shows only 5-10 suggestions. Collecting thousands of matches just to discard most of them is wasteful. Let's explore strategies for efficient result limiting.

Strategy 1: Early Termination

The simplest approach—stop collecting once you have enough results. Works well when you don't need ranking.

Strategy 2: Priority-Based Collection

If nodes store ranking information (popularity, recency), traverse in a way that finds the best results first.

Strategy 3: Bounded Heap

Use a min-heap of size K. As you traverse, add words to the heap. When full, only add if the new word is better than the worst in the heap.

limitedCollection.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import { MinHeap } from './heap';  // Assume we have a min-heap
 
interface RankedWord {
    word: string;
    score: number;
}
 
/**
 * Strategy 3: Bounded heap for top-K collection.
 * Efficiently finds the K highest-scored words without
 * collecting all words first.
 * 
 * Time: O(s log K) where s is subtree size
 * Space: O(K) for the heap
 */
function collectTopK(prefixNode: TrieNode, k: number): string[] {
    // Min-heap keeps track of top K (smallest of the top K at root)
    const minHeap = new MinHeap<RankedWord>(
        (a, b) => a.score - b.score  // Compare by score
    );
    
    const stack: TrieNode[] = [prefixNode];
    
    while (stack.length > 0) {
        const current = stack.pop()!;
        
        if (current.isEndOfWord && current.word !== null) {
            const candidate: RankedWord = {
                word: current.word,
                score: current.frequency  // Assume nodes store frequency
            };
            
            if (minHeap.size() < k) {
                // Haven't found k words yet, add unconditionally
                minHeap.push(candidate);
            } else if (candidate.score > minHeap.peek()!.score) {
                // This word is better than the worst in our top-K
                minHeap.pop();  // Remove worst
                minHeap.push(candidate);  // Add better one
            }
            // If score <= worst in heap, skip this word
        }
        
        for (const child of current.children.values()) {
            stack.push(child);
        }
    }
    
    // Extract results (will be in heap order, reverse for descending)
    const results: string[] = [];
    while (minHeap.size() > 0) {
        results.push(minHeap.pop()!.word);
    }
    
    return results.reverse();  // Best first
}
 
/**
 * Optimization: Branch pruning with max-score metadata.
 * If nodes store the maximum score of any descendant,
 * we can skip entire branches that can't compete.
 */
interface TrieNodeWithMaxScore extends TrieNode {
    maxDescendantScore: number;  // Max score in this subtree
}
 
function collectTopKOptimized(
    prefixNode: TrieNodeWithMaxScore, 
    k: number
): string[] {
    const minHeap = new MinHeap<RankedWord>(
        (a, b) => a.score - b.score
    );
    
    // Use priority queue for traversal - visit high-potential branches first
    const pq = new MaxHeap<TrieNodeWithMaxScore>(
        (a, b) => a.maxDescendantScore - b.maxDescendantScore
    );
    pq.push(prefixNode);
    
    while (pq.size() > 0) {
        const current = pq.pop()!;
        
        // Pruning: if this branch can't beat our worst top-K, skip it
        if (minHeap.size() >= k && 
            current.maxDescendantScore <= minHeap.peek()!.score) {
            continue;  // Skip entire branch
        }
        
        if (current.isEndOfWord && current.word !== null) {
            const candidate: RankedWord = {
                word: current.word,
                score: current.frequency
            };
            
            if (minHeap.size() < k) {
                minHeap.push(candidate);
            } else if (candidate.score > minHeap.peek()!.score) {
                minHeap.pop();
                minHeap.push(candidate);
            }
        }
        
        for (const child of current.children.values()) {
            pq.push(child as TrieNodeWithMaxScore);
        }
    }
    
    const results: string[] = [];
    while (minHeap.size() > 0) {
        results.push(minHeap.pop()!.word);
    }
    return results.reverse();
}

Comparison of Result Limiting Strategies
Strategy	Time Complexity	Quality	Implementation
Early termination	O(m + number_found)	Low (arbitrary results)	Simple
Collect all + sort + slice	O(m + s + s log s)	High (truly top-K)	Simple
Bounded heap (basic)	O(m + s log K)	High (truly top-K)	Medium
Bounded heap + pruning	O(m + visited log K)	High (truly top-K)	Complex

When Is Pruning Worth It?

Summary: Mastering Prefix Word Collection

We've thoroughly explored how to suggest all words with a given prefix—the fundamental operation behind autocomplete. Let's consolidate what we've learned:

Key Takeaways

•Two-phase algorithm — Navigate to the prefix node in O(m), then collect all words in the subtree in O(s). Total: O(m + s).
•DFS is the natural choice — Recursive DFS is clean and simple; iterative DFS handles deep tries and enables early termination.
•Complexity depends on the subtree — Short prefixes match many words, making collection expensive. Limit results in practice.
•Edge cases matter — Empty prefix, non-existent prefix, prefix-is-word, case sensitivity, and Unicode all need handling.
•Alphabetical order is achievable — Use sorted children structures or sort after collection.
•Top-K requires smarter collection — Bounded heaps, branch pruning, and priority-guided traversal find the best results efficiently.
•Early termination saves work — Don't collect 10,000 words to show 5 suggestions.

What's Next:

Page Complete

2 / 4