Search — Follow Path,… — Trie Operations — Insert,… | OneNoughtOne

0/97

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") \to 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") \to 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") \to 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\toa\tor\toe\tof, 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") \to 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") \to 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("") \to 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) \approx 20 string comparisons for each search. If strings average 10 characters, that's O(10 \times 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\toa\tor\toe 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'\to'p'\to... but you're looking for 'a'\to'p'\to... Normalization must be applied consistently across all operations.

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") \to 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") \to 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") \to 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\toa\tor\toe\tof, 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") \to 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") \to 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("") \to 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) \approx 20 string comparisons for each search. If strings average 10 characters, that's O(10 \times 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\toa\tor\toe 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'\to'p'\to... but you're looking for 'a'\to'p'\to... Normalization must be applied consistently across all operations.

Search — Follow Path, Check End-of-Word

Finding Needles in a Character Forest

Search Semantics: What "Found" Really Means

The Two Essential Conditions

The Mental Model: Paths vs. Words

The Search Algorithm: Step-by-Step

The Algorithm

Why Each Step Matters

Implementation: Array and Hash Map Versions

Array-Based Implementation

Hash Map-Based Implementation

Code Comment: Why the Implementations Are Nearly Identical

Traced Examples: Following the Path

Search 1: search("car") → true

Search 2: search("care") → true

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

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

Search 5: search("careful") → true

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

Time and Space Complexity Analysis

Time Complexity: O(m)

Space Complexity: O(1) Auxiliary

Early Termination: Best Case

Search vs. StartsWith: The Critical Distinction

Formal Definitions

The Key Difference: End-of-Word Check

Example: Trie with "application"

Edge Cases and Robustness

Edge Case 1: Search in Empty Trie

Edge Case 2: Search for Empty String

Edge Case 3: Search After Deletion

Edge Case 4: Case Sensitivity

There’s more to understand.

Search — Follow Path, Check End-of-Word

Finding Needles in a Character Forest

Search Semantics: What "Found" Really Means

The Two Essential Conditions

The Mental Model: Paths vs. Words

The Search Algorithm: Step-by-Step

The Algorithm

Why Each Step Matters

Implementation: Array and Hash Map Versions

Array-Based Implementation

Hash Map-Based Implementation

Code Comment: Why the Implementations Are Nearly Identical

Traced Examples: Following the Path

Search 1: search("car") → true

Search 2: search("care") → true

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

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

Search 5: search("careful") → true

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

Time and Space Complexity Analysis

Time Complexity: O(m)

Space Complexity: O(1) Auxiliary

Early Termination: Best Case

Search vs. StartsWith: The Critical Distinction

Formal Definitions

The Key Difference: End-of-Word Check

Example: Trie with "application"

Edge Cases and Robustness

Edge Case 1: Search in Empty Trie

Edge Case 2: Search for Empty String

Edge Case 3: Search After Deletion

Edge Case 4: Case Sensitivity

There’s more to understand.