Data Structures & AlgorithmsTrie Operations — Insert, Search, StartsWith

Trie Operations — Insert, Search, StartsWith

LevelIntermediate

Duration60 mins

TopicTrie Operations — Insert, Search, StartsWith

2 / 4

Search — Follow Path, Check End-of-Word

Finding Needles in a Character Forest

If insertion builds the trie, search answers the fundamental question every dictionary must answer: "Is this word in the collection?"

The search operation walks the same character-by-character path that insertion created. But whereas insertion creates nodes that don't exist, search must fail when it encounters a missing path. And even when the path exists completely, search must verify that the path represents a complete word, not merely a prefix of some longer word.

This page explores the search operation with the same rigor we applied to insertion. You'll understand the precise semantics of trie search, the two distinct failure modes, and how to implement bulletproof search logic that handles every edge case.

What You Will Master

By the end of this page, you will: (1) Understand the exact semantics of trie search and how it differs from startsWith, (2) Identify the two failure modes and implement proper checks for both, (3) Trace through searches step-by-step to build intuition, (4) Analyze time complexity and understand why it's O(m), (5) Handle edge cases and implement robust search logic.

Search Semantics: What "Found" Really Means

Before writing any code, we must precisely define what a successful search means. In a trie, search returns true if and only if the exact word was previously inserted.

This sounds simple, but the implications are subtle:

The Two Essential Conditions

For search(word) to return true, both conditions must hold:

The complete path exists: Every character in word has a corresponding edge from its parent node. We can walk the entire string without hitting a dead end.
The final node is marked as end-of-word: The node we land on after processing the last character has its isEndOfWord flag set to true.

Missing either condition means the word was not inserted:

Path Incomplete (Failure Mode 1)

•Trie contains: "apple"
•Search for: "application"
•Path a→p→p→l→e exists
•No edge for 'i' from 'e' node
•Result: false (path breaks)

Path Complete, Not End-of-Word (Failure Mode 2)

•Trie contains: "application"
•Search for: "apple"
•Path a→p→p→l→e exists!
•But 'e' node has isEndOfWord=false
•Result: false (not a complete word)

The Critical Distinction

Failure Mode 2 is the subtle one. Just because you can walk a path through the trie doesn't mean that path represents an inserted word. The path might exist only because it's a prefix of some longer word. The end-of-word marker is the definitive answer to "was this specific string inserted?"

The Mental Model: Paths vs. Words

Think of the trie as a city with roads. Every word we insert is like establishing a named location at the end of a series of roads. The roads (edges) exist and you can travel them, but only some destinations have street addresses (end-of-word markers).

Searching for a word is like asking: "Can I reach this address?" Two things can prevent you:

The roads don't go there: You hit a dead end before reaching the destination (path incomplete).
There's no address at that location: You can reach the physical spot, but nothing is registered there (path complete, not end-of-word).

Both mean the address doesn't exist—but for different reasons.

The Search Algorithm: Step-by-Step

The search algorithm mirrors insertion's path-walking logic but with crucial differences in how we handle missing children and what we return.

The Algorithm

Given a trie with root node root and a string word to search for:

Search Algorithm Steps

•Initialize current pointer: Set current = root.
•Iterate through each character: For each character c in word:
•Check if child exists: Look for a child of current corresponding to character c.
•If child doesn't exist, return false: The path is incomplete. The word cannot be in the trie.
•If child exists, advance: Move current to the child node.
•After loop, check end-of-word: Return current.isEndOfWord.

Why Each Step Matters

Steps 1-2: Identical to insertion. We're tracing the same path structure.

Steps 3-4 (Early Exit): This is where search diverges from insert. Insert creates missing children; search fails on missing children. If the path doesn't exist, the word was never inserted.

Step 5: Continue walking if the path exists.

Step 6 (Final Check): The crucial verification. We've confirmed the path exists; now we confirm it represents a complete word. Return the boolean directly—no need for if (isEndOfWord) return true else return false.

Elegance of the Final Check

Notice that step 6 simply returns isEndOfWord. This handles both success (true) and failure mode 2 (false) in a single expression. Don't overcomplicate with if-else when the flag is already a boolean that represents exactly what you need to return.

Implementation: Array and Hash Map Versions

Let's implement search for both children representations. The logic is identical; only the child lookup mechanism differs.

Array-Based Implementation

trie-search-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
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 the word is in the trie.
     * Time: O(m) where m is the length of the word
     * Space: O(1) - no additional space needed
     */
    search(word: string): boolean {
        let current = this.root;
        
        for (const char of word) {
            const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
            
            // Failure Mode 1: Path doesn't exist
            if (current.children[index] === null) {
                return false;
            }
            
            current = current.children[index]!;
        }
        
        // Failure Mode 2 handled implicitly:
        // Returns true only if this node marks end of word
        return current.isEndOfWord;
    }
}

Hash Map-Based Implementation

trie-search-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
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 the word is in the trie.
     * Time: O(m) where m is the length of the word
     * Space: O(1) - no additional space needed
     */
    search(word: string): boolean {
        let current = this.root;
        
        for (const char of word) {
            // Failure Mode 1: Path doesn't exist
            if (!current.children.has(char)) {
                return false;
            }
            
            current = current.children.get(char)!;
        }
        
        // Failure Mode 2 check: is this a complete word?
        return current.isEndOfWord;
    }
}

Code Comment: Why the Implementations Are Nearly Identical

Notice that the algorithm structure is exactly the same. The only difference is:

Array: current.children[index] === null vs current.children[index]!
Hash map: !current.children.has(char) vs current.children.get(char)!

This illustrates a powerful abstraction: the trie's logical behavior is independent of its physical representation. The children lookup is an implementation detail that doesn't affect the algorithm's correctness or complexity.

Traced Examples: Following the Path

Let's trace through searches on a trie containing: "cat", "car", "card", "care", "careful".

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

Search 1: search("car") → true

Step	Current Node	Character	Child Exists?	Action
1	root	'c'	Yes	Move to 'c' node
2	c	'a'	Yes	Move to 'a' node
3	a	'r'	Yes	Move to 'r' node
End	r	-	-	r.isEndOfWord = true → return true

Result: Found! Both conditions satisfied.

Search 2: search("care") → true

Step	Current Node	Character	Child Exists?	Action
1	root	'c'	Yes	Move to 'c' node
2	c	'a'	Yes	Move to 'a' node
3	a	'r'	Yes	Move to 'r' node
4	r	'e'	Yes	Move to 'e' node
End	e	-	-	e.isEndOfWord = true → return true

Result: Found! Note that 'e' node also has a child 'f' (for "careful"), but this doesn't affect the search—we stop at the end of our query string.

Search 3: search("caref") → false (Failure Mode 2)

Step	Current Node	Character	Child Exists?	Action
1	root	'c'	Yes	Move to 'c' node
2	c	'a'	Yes	Move to 'a' node
3	a	'r'	Yes	Move to 'r' node
4	r	'e'	Yes	Move to 'e' node
5	e	'f'	Yes	Move to 'f' node
End	f	-	-	f.isEndOfWord = false → return false

Result: Not found! The path exists completely, but "caref" was never inserted—only "careful" was. The 'f' node exists only as a stepping stone to 'u'.

Failure Mode 2 in Action

Search 3 demonstrates the critical importance of the end-of-word check. We successfully walked the entire path c→a→r→e→f, but that's not enough. The 'f' node was never marked as an end-of-word because no one inserted "caref". Always check isEndOfWord—the path existing is necessary but not sufficient.

Search 4: search("cab") → false (Failure Mode 1)

Step	Current Node	Character	Child Exists?	Action
1	root	'c'	Yes	Move to 'c' node
2	c	'a'	Yes	Move to 'a' node
3	a	'b'	No	Return false immediately

Result: Not found! The 'a' node has children 't' and 'r', but no 'b'. The path breaks before we finish processing the query string.

Search 5: search("careful") → true

Step	Current Node	Character	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
6	f	'u'	Yes	Move
7	u	'l'	Yes	Move
End	l	-	-	l.isEndOfWord = true → return true

Result: Found! We traversed the longest path in the trie and confirmed "careful" was inserted.

Search 6: search("") → depends on implementation

For an empty string, the loop executes zero times, and we check root.isEndOfWord. If we allowed inserting empty strings, this would return true. Otherwise, it returns false.

Practical advice: Either reject empty strings at insertion time, or document that search("") returns whether the empty string was explicitly inserted.

Time and Space Complexity Analysis

Time Complexity: O(m)

Where m is the length of the search query.

The algorithm processes each character exactly once (or exits early if the path breaks). At each character, we perform O(1) work:

Array lookup: children[index] is O(1)
Hash map lookup: children.has(char) is O(1) average

The final isEndOfWord check is also O(1).

Total: O(m)

Key insight: Search time is independent of how many words are in the trie. Whether the trie contains 100 words or 100 million words, searching for "algorithm" (m=9) takes the same time. This is a major advantage over balanced BSTs, where search time depends on the number of elements.

Search Time Comparison Across Data Structures
Data Structure	Search Time	Depends On
Trie	O(m)	Query length only
Hash Set	O(m)	Query length (for hashing)
Balanced BST	O(m log n)	Query length × log(# elements)
Sorted Array + Binary Search	O(m log n)	Query length × log(# elements)
Unsorted Array	O(n × m)	Linear scan, string comparison

Space Complexity: O(1) Auxiliary

Search uses only a constant amount of extra space:

One pointer (current) that walks down the trie
One loop counter (implicit in for...of)

We don't create any new nodes or allocate any data structures. The trie itself occupies space, but search doesn't add to it.

Early Termination: Best Case

If the query has a prefix that doesn't exist in the trie, we terminate early:

Search for "xyz..." in a trie with only "a..."-words: Returns after checking just the first character.
Worst case: The entire query path exists (or query is a suffix of an existing word that branches late).

In practice, early termination means many failed searches are faster than the full O(m).

Why O(m) Matters for Large Dictionaries

Consider a dictionary with 1 million words. A balanced BST would require O(log 1,000,000) ≈ 20 string comparisons for each search. If strings average 10 characters, that's O(10 × 20) = O(200) character comparisons. A trie needs only O(10) = 10 character lookups. For large dictionaries with long strings, tries provide a significant constant-factor improvement.

Search vs. StartsWith: The Critical Distinction

A common source of confusion is the difference between search and startsWith. Let's clarify with precision.

Formal Definitions

search(word): Returns true if and only if word was previously inserted as a complete word.

startsWith(prefix): Returns true if any word in the trie starts with prefix. The prefix itself need not be a complete word.

The Key Difference: End-of-Word Check

Search vs StartsWith Semantics
Aspect	search(word)	startsWith(prefix)
What it asks	"Was this exact word inserted?"	"Does any word begin with this?"
Path must exist	Yes	Yes
End-of-word required	Yes	No
Returns	current.isEndOfWord	true (if path exists)

Example: Trie with "application"

If we insert only "application":

Query	`search` Result	`startsWith` Result	Why
"application"	true	true	Full word, path exists, isEndOfWord=true
"app"	false	true	Path exists to 'p', but isEndOfWord=false
"apple"	false	false	Path breaks at 'l' (no edge from second 'p' to 'l')
""	false	true	Empty prefix matches everything

Critical observation: For "app", the path exists and if we were doing startsWith, we'd return true. But search must verify that "app" was explicitly inserted—which it wasn't. The 'p' node (at depth 3) exists only as part of the path to "application", not as a word terminus.

Implementation Hint

Many trie implementations factor out the path-walking logic into a private helper method that returns the node at the end of the path (or null if the path doesn't exist). Then search returns node.isEndOfWord if node exists, while startsWith returns node !== null. This DRYs up the code and makes the distinction crystal clear.

trie-dry-implementation.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
class Trie {
    private root: TrieNode;
    
    constructor() {
        this.root = new TrieNode();
    }
    
    /**
     * Private helper: walks the path and returns the terminal node.
     * Returns null if the path doesn't exist.
     */
    private findNode(str: string): TrieNode | null {
        let current = this.root;
        
        for (const char of str) {
            if (!current.children.has(char)) {
                return null;  // Path breaks
            }
            current = current.children.get(char)!;
        }
        
        return current;  // Path exists, return terminal node
    }
    
    /**
     * Search: exact word match
     */
    search(word: string): boolean {
        const node = this.findNode(word);
        return node !== null && node.isEndOfWord;
    }
    
    /**
     * StartsWith: prefix match
     */
    startsWith(prefix: string): boolean {
        return this.findNode(prefix) !== null;
    }
}

This refactored implementation makes the semantic difference explicit:

search needs the node to exist AND be an end-of-word
startsWith only needs the node to exist

The shared path-walking logic is in findNode, eliminating duplication and potential for bugs.

Edge Cases and Robustness

Edge Case 1: Search in Empty Trie

Searching for any word in an empty trie (no insertions):

The root exists but has no children.
Any query with at least one character will fail at the first character (no child exists).
Exception: search("") returns root.isEndOfWord, which is false unless you explicitly allow empty string insertion.

Behavior: Correctly returns false for all non-empty queries.

Edge Case 2: Search for Empty String

search("") executes zero loop iterations and returns root.isEndOfWord.

If you inserted "": Returns true. If you didn't insert "" (or disallow it): Returns false.

Best practice: Decide your API contract and document it. Most implementations either reject empty strings at insertion or return false for empty search queries.

Edge Case 3: Search After Deletion

If your trie supports deletion, be aware:

Deleting "care" should make search("care") return false.
But what about "careful"? If "careful" is still in the trie, the path c→a→r→e must remain—only the isEndOfWord flag at 'e' should be cleared.

Deletion is more complex than search and will be covered in advanced trie operations. The key insight here is that search depends on the current state of the trie, which may change if you implement deletion.

Edge Case 4: Case Sensitivity

By default, tries are case-sensitive. "Apple" and "apple" are different words with different paths.

For case-insensitive search:

trie-case-insensitive.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Case-insensitive search.
 * Normalizes the query to lowercase before searching.
 */
search(word: string): boolean {
    // Normalize to lowercase for case-insensitive matching
    return this.searchInternal(word.toLowerCase());
}
 
/**
 * Insert should also normalize to lowercase.
 */
insert(word: string): void {
    this.insertInternal(word.toLowerCase());
}

Consistency is Key

If you normalize queries in search, you MUST normalize during insertion too. Otherwise, inserting "Apple" and searching for "apple" will fail because the trie stores 'A'→'p'→... but you're looking for 'a'→'p'→... Normalization must be applied consistently across all operations.

Summary: Mastering Trie Search

We've dissected the trie search operation with surgical precision. Here are the essential takeaways:

Key Takeaways

•Search has two success conditions: The complete path must exist AND the terminal node must be marked as end-of-word.
•Two failure modes: Path breaks (character not found) or path complete but not end-of-word (prefix only).
•Time complexity is O(m): Independent of trie size. Query length is the only factor.
•Space complexity is O(1): Search only needs a pointer to walk the tree.
•Search ≠ StartsWith: Search requires end-of-word; startsWith only requires path existence.
•Factor out path-walking: Use a helper method to avoid code duplication between search and startsWith.
•Handle edge cases: Empty strings, empty tries, and case sensitivity require explicit decisions.

What's Next:

The next page explores startsWith—the prefix matching operation that distinguishes tries from hash sets. While the algorithm is nearly identical to search, the semantics and use cases differ profoundly. We'll see why startsWith is the operation that makes tries irreplaceable for autocomplete, spell check, and prefix-based filtering.

Page Complete

You now understand trie search at an expert level. You can explain the two failure modes, trace through searches step by step, implement search for both array and hash map representations, and articulate the precise difference between search and startsWith. Next: the prefix matching operation that makes tries special.

2 / 4

Loading learning content...

Data Structures & AlgorithmsTrie Operations — Insert, Search, StartsWith

Trie Operations — Insert, Search, StartsWith

LevelIntermediate

Duration60 mins

TopicTrie Operations — Insert, Search, StartsWith

2 / 4

Search — Follow Path, Check End-of-Word

Finding Needles in a Character Forest

If insertion builds the trie, search answers the fundamental question every dictionary must answer: "Is this word in the collection?"

What You Will Master

Search Semantics: What "Found" Really Means

Before writing any code, we must precisely define what a successful search means. In a trie, search returns true if and only if the exact word was previously inserted.

This sounds simple, but the implications are subtle:

The Two Essential Conditions

For search(word) to return true, both conditions must hold:

The complete path exists: Every character in word has a corresponding edge from its parent node. We can walk the entire string without hitting a dead end.
The final node is marked as end-of-word: The node we land on after processing the last character has its isEndOfWord flag set to true.

Missing either condition means the word was not inserted:

Path Incomplete (Failure Mode 1)

•Trie contains: "apple"
•Search for: "application"
•Path a→p→p→l→e exists
•No edge for 'i' from 'e' node
•Result: false (path breaks)

Path Complete, Not End-of-Word (Failure Mode 2)

•Trie contains: "application"
•Search for: "apple"
•Path a→p→p→l→e exists!
•But 'e' node has isEndOfWord=false
•Result: false (not a complete word)

The Critical Distinction

The Mental Model: Paths vs. Words

Searching for a word is like asking: "Can I reach this address?" Two things can prevent you:

The roads don't go there: You hit a dead end before reaching the destination (path incomplete).
There's no address at that location: You can reach the physical spot, but nothing is registered there (path complete, not end-of-word).

Both mean the address doesn't exist—but for different reasons.

The Search Algorithm: Step-by-Step

The search algorithm mirrors insertion's path-walking logic but with crucial differences in how we handle missing children and what we return.

The Algorithm

Given a trie with root node root and a string word to search for:

Search Algorithm Steps

•Initialize current pointer: Set current = root.
•Iterate through each character: For each character c in word:
•Check if child exists: Look for a child of current corresponding to character c.
•If child doesn't exist, return false: The path is incomplete. The word cannot be in the trie.
•If child exists, advance: Move current to the child node.
•After loop, check end-of-word: Return current.isEndOfWord.

Why Each Step Matters

Steps 1-2: Identical to insertion. We're tracing the same path structure.

Steps 3-4 (Early Exit): This is where search diverges from insert. Insert creates missing children; search fails on missing children. If the path doesn't exist, the word was never inserted.

Step 5: Continue walking if the path exists.

Elegance of the Final Check

Implementation: Array and Hash Map Versions

Let's implement search for both children representations. The logic is identical; only the child lookup mechanism differs.

Array-Based Implementation

trie-search-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
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 the word is in the trie.
     * Time: O(m) where m is the length of the word
     * Space: O(1) - no additional space needed
     */
    search(word: string): boolean {
        let current = this.root;
        
        for (const char of word) {
            const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
            
            // Failure Mode 1: Path doesn't exist
            if (current.children[index] === null) {
                return false;
            }
            
            current = current.children[index]!;
        }
        
        // Failure Mode 2 handled implicitly:
        // Returns true only if this node marks end of word
        return current.isEndOfWord;
    }
}

Hash Map-Based Implementation

trie-search-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
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 the word is in the trie.
     * Time: O(m) where m is the length of the word
     * Space: O(1) - no additional space needed
     */
    search(word: string): boolean {
        let current = this.root;
        
        for (const char of word) {
            // Failure Mode 1: Path doesn't exist
            if (!current.children.has(char)) {
                return false;
            }
            
            current = current.children.get(char)!;
        }
        
        // Failure Mode 2 check: is this a complete word?
        return current.isEndOfWord;
    }
}

Code Comment: Why the Implementations Are Nearly Identical

Notice that the algorithm structure is exactly the same. The only difference is:

Array: current.children[index] === null vs current.children[index]!
Hash map: !current.children.has(char) vs current.children.get(char)!

Traced Examples: Following the Path

Let's trace through searches on a trie containing: "cat", "car", "card", "care", "careful".

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

Search 1: search("car") → true

Step	Current Node	Character	Child Exists?	Action
1	root	'c'	Yes	Move to 'c' node
2	c	'a'	Yes	Move to 'a' node
3	a	'r'	Yes	Move to 'r' node
End	r	-	-	r.isEndOfWord = true → return true

Result: Found! Both conditions satisfied.

Search 2: search("care") → true

Step	Current Node	Character	Child Exists?	Action
1	root	'c'	Yes	Move to 'c' node
2	c	'a'	Yes	Move to 'a' node
3	a	'r'	Yes	Move to 'r' node
4	r	'e'	Yes	Move to 'e' node
End	e	-	-	e.isEndOfWord = true → return true

Result: Found! Note that 'e' node also has a child 'f' (for "careful"), but this doesn't affect the search—we stop at the end of our query string.

Search 3: search("caref") → false (Failure Mode 2)

Step	Current Node	Character	Child Exists?	Action
1	root	'c'	Yes	Move to 'c' node
2	c	'a'	Yes	Move to 'a' node
3	a	'r'	Yes	Move to 'r' node
4	r	'e'	Yes	Move to 'e' node
5	e	'f'	Yes	Move to 'f' node
End	f	-	-	f.isEndOfWord = false → return false

Result: Not found! The path exists completely, but "caref" was never inserted—only "careful" was. The 'f' node exists only as a stepping stone to 'u'.

Failure Mode 2 in Action

Search 4: search("cab") → false (Failure Mode 1)

Step	Current Node	Character	Child Exists?	Action
1	root	'c'	Yes	Move to 'c' node
2	c	'a'	Yes	Move to 'a' node
3	a	'b'	No	Return false immediately

Result: Not found! The 'a' node has children 't' and 'r', but no 'b'. The path breaks before we finish processing the query string.

Search 5: search("careful") → true

Step	Current Node	Character	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
6	f	'u'	Yes	Move
7	u	'l'	Yes	Move
End	l	-	-	l.isEndOfWord = true → return true

Result: Found! We traversed the longest path in the trie and confirmed "careful" was inserted.

Search 6: search("") → depends on implementation

For an empty string, the loop executes zero times, and we check root.isEndOfWord. If we allowed inserting empty strings, this would return true. Otherwise, it returns false.

Practical advice: Either reject empty strings at insertion time, or document that search("") returns whether the empty string was explicitly inserted.

Time and Space Complexity Analysis

Time Complexity: O(m)

Where m is the length of the search query.

The algorithm processes each character exactly once (or exits early if the path breaks). At each character, we perform O(1) work:

Array lookup: children[index] is O(1)
Hash map lookup: children.has(char) is O(1) average

The final isEndOfWord check is also O(1).

Total: O(m)

Search Time Comparison Across Data Structures
Data Structure	Search Time	Depends On
Trie	O(m)	Query length only
Hash Set	O(m)	Query length (for hashing)
Balanced BST	O(m log n)	Query length × log(# elements)
Sorted Array + Binary Search	O(m log n)	Query length × log(# elements)
Unsorted Array	O(n × m)	Linear scan, string comparison

Space Complexity: O(1) Auxiliary

Search uses only a constant amount of extra space:

One pointer (current) that walks down the trie
One loop counter (implicit in for...of)

We don't create any new nodes or allocate any data structures. The trie itself occupies space, but search doesn't add to it.

Early Termination: Best Case

If the query has a prefix that doesn't exist in the trie, we terminate early:

Search for "xyz..." in a trie with only "a..."-words: Returns after checking just the first character.
Worst case: The entire query path exists (or query is a suffix of an existing word that branches late).

In practice, early termination means many failed searches are faster than the full O(m).

Why O(m) Matters for Large Dictionaries

Search vs. StartsWith: The Critical Distinction

A common source of confusion is the difference between search and startsWith. Let's clarify with precision.

Formal Definitions

search(word): Returns true if and only if word was previously inserted as a complete word.

startsWith(prefix): Returns true if any word in the trie starts with prefix. The prefix itself need not be a complete word.

The Key Difference: End-of-Word Check

Search vs StartsWith Semantics
Aspect	search(word)	startsWith(prefix)
What it asks	"Was this exact word inserted?"	"Does any word begin with this?"
Path must exist	Yes	Yes
End-of-word required	Yes	No
Returns	current.isEndOfWord	true (if path exists)

Example: Trie with "application"

If we insert only "application":

Query	`search` Result	`startsWith` Result	Why
"application"	true	true	Full word, path exists, isEndOfWord=true
"app"	false	true	Path exists to 'p', but isEndOfWord=false
"apple"	false	false	Path breaks at 'l' (no edge from second 'p' to 'l')
""	false	true	Empty prefix matches everything

Implementation Hint

trie-dry-implementation.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
class Trie {
    private root: TrieNode;
    
    constructor() {
        this.root = new TrieNode();
    }
    
    /**
     * Private helper: walks the path and returns the terminal node.
     * Returns null if the path doesn't exist.
     */
    private findNode(str: string): TrieNode | null {
        let current = this.root;
        
        for (const char of str) {
            if (!current.children.has(char)) {
                return null;  // Path breaks
            }
            current = current.children.get(char)!;
        }
        
        return current;  // Path exists, return terminal node
    }
    
    /**
     * Search: exact word match
     */
    search(word: string): boolean {
        const node = this.findNode(word);
        return node !== null && node.isEndOfWord;
    }
    
    /**
     * StartsWith: prefix match
     */
    startsWith(prefix: string): boolean {
        return this.findNode(prefix) !== null;
    }
}

This refactored implementation makes the semantic difference explicit:

search needs the node to exist AND be an end-of-word
startsWith only needs the node to exist

The shared path-walking logic is in findNode, eliminating duplication and potential for bugs.

Edge Cases and Robustness

Edge Case 1: Search in Empty Trie

Searching for any word in an empty trie (no insertions):

The root exists but has no children.
Any query with at least one character will fail at the first character (no child exists).
Exception: search("") returns root.isEndOfWord, which is false unless you explicitly allow empty string insertion.

Behavior: Correctly returns false for all non-empty queries.

Edge Case 2: Search for Empty String

search("") executes zero loop iterations and returns root.isEndOfWord.

If you inserted "": Returns true. If you didn't insert "" (or disallow it): Returns false.

Best practice: Decide your API contract and document it. Most implementations either reject empty strings at insertion or return false for empty search queries.

Edge Case 3: Search After Deletion

If your trie supports deletion, be aware:

Deleting "care" should make search("care") return false.
But what about "careful"? If "careful" is still in the trie, the path c→a→r→e must remain—only the isEndOfWord flag at 'e' should be cleared.

Edge Case 4: Case Sensitivity

By default, tries are case-sensitive. "Apple" and "apple" are different words with different paths.

For case-insensitive search:

trie-case-insensitive.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Case-insensitive search.
 * Normalizes the query to lowercase before searching.
 */
search(word: string): boolean {
    // Normalize to lowercase for case-insensitive matching
    return this.searchInternal(word.toLowerCase());
}
 
/**
 * Insert should also normalize to lowercase.
 */
insert(word: string): void {
    this.insertInternal(word.toLowerCase());
}

Consistency is Key

Summary: Mastering Trie Search

We've dissected the trie search operation with surgical precision. Here are the essential takeaways:

Key Takeaways

•Search has two success conditions: The complete path must exist AND the terminal node must be marked as end-of-word.
•Two failure modes: Path breaks (character not found) or path complete but not end-of-word (prefix only).
•Time complexity is O(m): Independent of trie size. Query length is the only factor.
•Space complexity is O(1): Search only needs a pointer to walk the tree.
•Search ≠ StartsWith: Search requires end-of-word; startsWith only requires path existence.
•Factor out path-walking: Use a helper method to avoid code duplication between search and startsWith.
•Handle edge cases: Empty strings, empty tries, and case sensitivity require explicit decisions.

What's Next:

Page Complete

2 / 4