Trie Operations - Learning Module

Loading content...

0/276

StartsWith — Follow Path, Don't Require End-of-Word

The Operation That Makes Tries Irreplaceable

If search answers "Is this word in the dictionary?" then startsWith answers a fundamentally different question: "Are there any words that begin with this prefix?"

This seemingly simple distinction is what elevates tries from a mere alternative to hash sets into a category of their own. Hash tables excel at exact match—given a key, retrieve a value. But they are helpless for prefix-based queries. To find all words starting with "auto", a hash set would need to iterate through every word, checking each one. That's O(n × m) where n is the dictionary size.

A trie answers the same question in O(m) time—just the length of the prefix. The existence of a path for "a-u-t-o" tells us instantly whether any words with that prefix exist. This capability powers:

Autocomplete systems in search engines and IDEs
Spell checkers suggesting corrections
Prefix-based filtering in address books and file browsers
IP routing tables matching address prefixes
Command-line tab completion

This page explores startsWith in depth—its semantics, implementation, relationship to search, and the powerful applications it enables.

What You Will Master

By the end of this page, you will: (1) Understand exactly what startsWith queries and why it differs from search, (2) Implement startsWith and explain why it's simpler than search, (3) Trace through prefix queries and predict results, (4) Leverage startsWith as a foundation for autocomplete, (5) Recognize the computational advantage tries provide for prefix operations.

Prefix vs. Word: Semantic Precision

Before examining the algorithm, we must be crystal clear about what startsWith actually asks.

The Formal Definition

startsWith(prefix) returns true if and only if there exists at least one word in the trie such that word.startsWith(prefix).

Equivalently: The path corresponding to prefix exists in the trie.

What This Means

The existence of a path for prefix p means one of two things (or both):

The prefix itself is a word: p was inserted, so there's an end-of-word marker at the path's terminus.
The prefix leads to longer words: Other words were inserted that have p as their prefix, so nodes exist beyond p's terminus.

Either case makes startsWith(p) return true. The key insight: startsWith doesn't care about end-of-word markers at all. It only cares whether the path exists.

search("app")

•Asks: "Was 'app' inserted?"
•Requires: path a→p→p exists
•Requires: isEndOfWord = true at 'p' node
•If only 'apple' was inserted: false
•If 'app' was inserted: true

startsWith("app")

•Asks: "Are there words starting with 'app'?"
•Requires: path a→p→p exists
•Does NOT require: isEndOfWord at any node
•If only 'apple' was inserted: true
•If 'app' was inserted: true

The Subtle Truth

If search(word) is true, then startsWith(word) is also true. A complete word is always a valid prefix of itself.

But the converse is not true: startsWith(prefix) being true does not imply search(prefix) is true. The prefix might exist only as a path segment toward longer words.

In set notation:

Let W = set of inserted words
search(s) = s ∈ W
startsWith(p) = ∃w ∈ W such that w starts with p

For any word w: w ∈ W ⟹ w starts with w ⟹ startsWith(w) is true.

But startsWith(p) true does not mean p ∈ W.

Edge Case: Empty Prefix

startsWith("") is always true for a non-empty trie. Every word starts with the empty prefix. The empty string is the universal prefix. If your trie has at least one word, startsWith("") returns true. Even for an empty trie, you might consider returning true since there's no word that doesn't start with ""—though this is a philosophical edge case most implementations handle by returning true.

The StartsWith Algorithm: Elegant Simplicity

The startsWith algorithm is remarkably simple—simpler than search, in fact. We walk the trie following the prefix characters. If we reach the end of the prefix without hitting a missing edge, we return true.

The Algorithm

Given a trie with root root and prefix prefix to check:

StartsWith Algorithm Steps

•Initialize current pointer: Set current = root.
•Iterate through each character: For each character c in prefix:
•Check if child exists: Look for a child of current corresponding to c.
•If child doesn't exist, return false: The prefix has no matching path.
•If child exists, advance: Move current to that child.
•After loop, return true: We successfully walked the entire prefix.

What's Missing Compared to Search?

Notice what's absent: there's no end-of-word check at the end. The algorithm just returns true after successfully walking the path. We don't care whether the node we land on marks a complete word—we only care that we got there.

This single difference encapsulates the semantic distinction between search and startsWith.

startswith-comparison.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
// Search: path must exist AND node must be end-of-word
search(word: string): boolean {
    const node = this.walkPath(word);
    return node !== null && node.isEndOfWord;  // <-- End-of-word check
}
 
// StartsWith: path must exist, that's it
startsWith(prefix: string): boolean {
    const node = this.walkPath(prefix);
    return node !== null;  // <-- No end-of-word check
}
 
// Shared path-walking logic
private walkPath(str: string): TrieNode | null {
    let current = this.root;
    for (const char of str) {
        if (!current.children.has(char)) {
            return null;
        }
        current = current.children.get(char)!;
    }
    return current;
}

The Elegance of Shared Logic

By factoring out the path-walking into a helper method, we see that search and startsWith are identical except for one line. This isn't just DRY code—it's a conceptual revelation. Both operations are fundamentally about path existence; they differ only in what additional property they require at the terminal node.

Full Implementation: Both Representations

Let's provide complete, production-ready implementations for both array-based and hash map-based tries.

Array-Based Implementation

startswith-array.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
class TrieNode {
    children: (TrieNode | null)[];
    isEndOfWord: boolean;
    
    constructor() {
        this.children = new Array(26).fill(null);
        this.isEndOfWord = false;
    }
}
 
class Trie {
    private root: TrieNode;
    
    constructor() {
        this.root = new TrieNode();
    }
    
    /**
     * Returns true if there is any word in the trie
     * that starts with the given prefix.
     * 
     * Time: O(m) where m is prefix length
     * Space: O(1)
     */
    startsWith(prefix: string): boolean {
        let current = this.root;
        
        for (const char of prefix) {
            const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
            
            // Path breaks - no words with this prefix
            if (current.children[index] === null) {
                return false;
            }
            
            current = current.children[index]!;
        }
        
        // We walked the entire prefix - words exist
        return true;
    }
}

Hash Map-Based Implementation

startswith-hashmap.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
class TrieNode {
    children: Map<string, TrieNode>;
    isEndOfWord: boolean;
    
    constructor() {
        this.children = new Map();
        this.isEndOfWord = false;
    }
}
 
class Trie {
    private root: TrieNode;
    
    constructor() {
        this.root = new TrieNode();
    }
    
    /**
     * Returns true if there is any word in the trie
     * that starts with the given prefix.
     * 
     * Time: O(m) where m is prefix length
     * Space: O(1)
     */
    startsWith(prefix: string): boolean {
        let current = this.root;
        
        for (const char of prefix) {
            // Path breaks - no words with this prefix
            if (!current.children.has(char)) {
                return false;
            }
            
            current = current.children.get(char)!;
        }
        
        // We walked the entire prefix - words exist
        return true;
    }
}

Complete Trie Class with All Operations

Here's a cohesive implementation combining insert, search, and startsWith with shared logic:

complete-trie.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
class TrieNode {
    children: Map<string, TrieNode>;
    isEndOfWord: boolean;
    
    constructor() {
        this.children = new Map();
        this.isEndOfWord = false;
    }
}
 
class Trie {
    private root: TrieNode;
    
    constructor() {
        this.root = new TrieNode();
    }
    
    /**
     * Inserts a word into the trie.
     * Time: O(m), Space: O(m) worst case
     */
    insert(word: string): void {
        let current = this.root;
        for (const char of word) {
            if (!current.children.has(char)) {
                current.children.set(char, new TrieNode());
            }
            current = current.children.get(char)!;
        }
        current.isEndOfWord = true;
    }
    
    /**
     * Returns true if the word is in the trie (exact match).
     * Time: O(m), Space: O(1)
     */
    search(word: string): boolean {
        const node = this.findNode(word);
        return node !== null && node.isEndOfWord;
    }
    
    /**
     * Returns true if any word starts with the given prefix.
     * Time: O(m), Space: O(1)
     */
    startsWith(prefix: string): boolean {
        return this.findNode(prefix) !== null;
    }
    
    /**
     * Private helper: walks the trie following the string.
     * Returns the terminal node or null if path breaks.
     */
    private findNode(str: string): TrieNode | null {
        let current = this.root;
        for (const char of str) {
            if (!current.children.has(char)) {
                return null;
            }
            current = current.children.get(char)!;
        }
        return current;
    }
}

Traced Examples: Prefix Queries in Action

Let's trace through startsWith queries on our familiar trie containing: "cat", "car", "card", "care", "careful".

root
└── c
    └── a
        ├── t [END]
        └── r [END]
            ├── d [END]
            └── e [END]
                └── f
                    └── u
                        └── l [END]

Query 1: startsWith("car") → true

Step	Current	Char	Child Exists?	Action
1	root	'c'	Yes	Move to 'c'
2	c	'a'	Yes	Move to 'a'
3	a	'r'	Yes	Move to 'r'
End	-	-	-	Return true

Result: True. The path exists. Words starting with "car": "car", "card", "care", "careful".

Query 2: startsWith("caref") → true

Step	Current	Char	Child Exists?	Action
1	root	'c'	Yes	Move
2	c	'a'	Yes	Move
3	a	'r'	Yes	Move
4	r	'e'	Yes	Move
5	e	'f'	Yes	Move to 'f'
End	-	-	-	Return true

Result: True. Even though "caref" itself is not a word (search("caref") = false), words starting with "caref" exist ("careful").

This is the crucial difference: startsWith("caref") is true because the path exists and leads to "careful". search("caref") is false because "caref" was never inserted.

Query 3: startsWith("cab") → false

Step	Current	Char	Child Exists?	Action
1	root	'c'	Yes	Move
2	c	'a'	Yes	Move
3	a	'b'	No	Return false

Result: False. No words start with "cab". The 'a' node has children 't' and 'r', but not 'b'.

Query 4: startsWith("careful") → true

Full path c→a→r→e→f→u→l exists. "careful" is both a prefix that exists and a complete word.

Query 5: startsWith("carefulx") → false

Path c→a→r→e→f→u→l exists, but there's no 'x' child at 'l' node. No words start with "carefulx".

Query 6: startsWith("") → true

The loop executes zero times. We return true immediately. Every word starts with the empty prefix.

Intuition Builder

Think of startsWith as asking: "If I start typing this prefix, is autocomplete going to show me anything?" If the path exists, there are completions. If not, the prefix is a dead end—no word in the dictionary begins with those characters in that order.

Complexity Analysis: The O(m) Advantage

Time Complexity: O(m)

Where m is the length of the prefix.

Identical to search. We iterate through each character at most once, performing O(1) work per character (child lookup). The final return is O(1).

Key insight: The time is independent of:

How many words are in the trie (n)
How many words match the prefix (could be 0, 1, or millions)

We're just checking if the path exists, not counting or listing matches.

Why This Matters: Comparison with Alternatives

Suppose we have a dictionary of n words and want to check if any word starts with a prefix of length m.

Prefix Query Performance Across Data Structures
Data Structure	Time Complexity	Notes
Trie	O(m)	Just walk the prefix path
Hash Set	O(n × m)	Must check every word
Sorted Array + Binary Search	O(m × log n)	Binary search, then verify prefix
Unsorted Array	O(n × m)	Linear scan, prefix check each

Example with n=1,000,000 words, m=5 prefix:

Trie: O(5) = 5 operations
Hash set: O(1,000,000 × 5) = 5,000,000 operations
Sorted array: O(5 × 20) = 100 operations (log₂(10⁶) ≈ 20)

For prefix queries, tries outperform hash sets by orders of magnitude. Even sorted arrays with binary search still depend on n.

When This Advantage Matters Most

The O(m) complexity shines for interactive applications where prefix queries happen frequently (every keystroke in autocomplete). Reducing from O(log n) to O(m) might seem minor, but when m is typically 1-3 characters and n is millions, the difference is significant. And compared to O(n) operations, it's transformative.

Space Complexity: O(1) Auxiliary

Like search, startsWith only needs a pointer to walk the trie. No additional data structures are created.

Beyond Boolean: Finding All Words with a Prefix

The basic startsWith returns a boolean. But the real power lies in the next step: retrieving all words that match the prefix.

This is what powers autocomplete. When you type "prog", the system doesn't just confirm words exist—it lists them: "program", "programming", "progress", "programmer", etc.

The Two-Phase Approach

Phase 1: Use startsWith logic to navigate to the node at the end of the prefix. If it doesn't exist, return an empty list.
Phase 2: From that node, perform a DFS (depth-first search) to collect all words in the subtrie rooted at that node.

get-words-with-prefix.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
class Trie {
    private root: TrieNode;
    
    // ... constructor, insert, search, startsWith ...
    
    /**
     * Returns all words in the trie that start with the given prefix.
     * Time: O(m + k) where m is prefix length, k is total characters
     *       in all matching words after the prefix
     * Space: O(max word length) for recursion stack, plus output array
     */
    getWordsWithPrefix(prefix: string): string[] {
        // Phase 1: Navigate to prefix node
        let current = this.root;
        for (const char of prefix) {
            if (!current.children.has(char)) {
                return [];  // No words with this prefix
            }
            current = current.children.get(char)!;
        }
        
        // Phase 2: Collect all words from this subtrie
        const results: string[] = [];
        this.collectWords(current, prefix, results);
        return results;
    }
    
    /**
     * DFS helper to collect all words rooted at the given node.
     * Uses currentWord as the accumulated string so far.
     */
    private collectWords(
        node: TrieNode,
        currentWord: string,
        results: string[]
    ): void {
        // If this node marks a complete word, add it
        if (node.isEndOfWord) {
            results.push(currentWord);
        }
        
        // Recursively explore all children
        for (const [char, childNode] of node.children) {
            this.collectWords(childNode, currentWord + char, results);
        }
    }
}

Complexity Analysis for getWordsWithPrefix

Time Complexity: O(m + k)

O(m) to navigate to the prefix node
O(k) to traverse the subtrie, where k is the total number of characters in all matching words (past the prefix)

Space Complexity: O(L + r × L)

O(L) for recursion stack depth (L = longest word length)
O(r × L) for output array (r = number of matching words)

Why this is efficient: We only visit nodes that are actually in the subtrie. For a prefix with few matches, this is fast. The traversal is proportional to the output size—can't do better than that when you need to enumerate results.

Limiting Results for Autocomplete

In practice, autocomplete shows only the top 5-10 suggestions. Modify collectWords to stop after finding k words, or use a priority queue to return most frequent/relevant matches. For production systems, combine with frequency data stored in nodes.

Practical Applications of StartsWith

Let's examine real-world systems where startsWith (and its extensions) provide critical functionality.

Application 1: Search Engine Autocomplete

As users type, the search box predicts completions.

Challenge: Millions of possible queries; must respond in <100ms.

Solution: Trie stores popular queries. Each keystroke triggers startsWith + getWordsWithPrefix. Frequency counts at nodes enable ranking.

Application 2: IDE Code Completion

When you type str., the IDE suggests methods like startsWith, substring, split.

Challenge: Symbol tables can be huge; language servers must be fast.

Solution: Tries index method names. Typing filters instantly via prefix matching.

Application 3: Contact/Address Book Search

Typing "Jo" shows "John", "Jonathan", "Joanna".

Challenge: Must update results after each keystroke.

Solution: Names stored in trie. Single-character prefixes return quickly even with thousands of contacts.

StartsWith Applications Summary
Application	Prefix Query Use	Why Tries Excel
Search autocomplete	Suggest queries as user types	O(m) regardless of dictionary size
Code completion	Filter symbols by typed prefix	Instant updates per keystroke
Spell check	Suggest corrections starting with partial word	Efficient prefix enumeration
IP routing	Match address to longest prefix	Packet routing in microseconds
Dictionary browser	Show words starting with selection	Smooth scroll through filtered list
File path completion	Complete paths in terminal/file dialog	Fast even with deep directory trees

Common Pattern: Incremental Refinement

Many applications share this pattern:

User types first character → startsWith with 1-char prefix → filter to subset
User types second character → startsWith with 2-char prefix → filter further
Continue until user selects or finishes typing

Each step is O(m), and m is incrementing by 1 each time. The trie naturally supports this incremental refinement without preprocessing or caching—though caching the "current node" across keystrokes can eliminate re-walking the path.

incremental-autocomplete.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
/**
 * Optimized autocomplete that maintains cursor position.
 * Avoids re-walking the trie from root on each keystroke.
 */
class IncrementalAutocomplete {
    private trie: Trie;
    private currentNode: TrieNode | null;
    private currentPrefix: string;
    
    constructor(words: string[]) {
        this.trie = new Trie();
        words.forEach(word => this.trie.insert(word));
        this.reset();
    }
    
    /**
     * User typed a character. Advance the cursor if possible.
     */
    type(char: string): string[] {
        if (this.currentNode === null) {
            return [];  // Already in dead-end state
        }
        
        if (!this.currentNode.children.has(char)) {
            this.currentNode = null;  // Dead end
            return [];
        }
        
        this.currentNode = this.currentNode.children.get(char)!;
        this.currentPrefix += char;
        
        return this.getSuggestions();
    }
    
    /**
     * User deleted a character. Walk from root to new prefix.
     */
    backspace(): string[] {
        if (this.currentPrefix.length === 0) {
            return this.getSuggestions();
        }
        
        this.currentPrefix = this.currentPrefix.slice(0, -1);
        
        // Re-walk to new prefix (could optimize with parent pointers)
        this.currentNode = this.trie.getNode(this.currentPrefix);
        
        return this.getSuggestions();
    }
    
    private getSuggestions(): string[] {
        if (this.currentNode === null) return [];
        return this.trie.getWordsFromNode(this.currentNode, this.currentPrefix);
    }
    
    reset(): void {
        this.currentNode = this.trie.getRoot();
        this.currentPrefix = "";
    }
}

Summary: The Power of Prefix Matching

The startsWith operation encapsulates why tries exist. Let's consolidate what we've learned:

Key Takeaways

•StartsWith asks a different question than search: "Are there words beginning with this?" vs "Was this exact word inserted?"
•The algorithm is simpler than search: Walk the path; if it exists, return true. No end-of-word check needed.
•Time complexity O(m) is independent of dictionary size: This is the killer feature for prefix operations.
•Hash tables cannot compete for prefix queries: They require O(n × m) linear scans.
•StartsWith is the foundation for autocomplete: Combine with DFS to enumerate all matching words.
•Incremental refinement is natural: Each new character just extends the path by one node.
•Empty prefix is the universal match: startsWith("") is true for any non-empty trie.

What's Next:

Now that we understand all three core operations—insert, search, and startsWith—the next page brings everything together with a comprehensive time complexity analysis. We'll rigorously verify the O(m) bound, explore how it compares to alternatives in different scenarios, and understand when tries are the optimal choice versus when other data structures might suffice.

Page Complete

You've mastered the startsWith operation—the capability that makes tries irreplaceable for prefix-based queries. You understand its semantics, implementation, O(m) complexity, and real-world applications. Combined with insert and search, you now have a complete mental model of trie operations. Next: formal complexity analysis.