Implement Trie (Prefix Tree)

medium · trie, strings

Implement Trie (Prefix Tree)

Implement a trie that supports inserting words, searching for a complete word, and checking whether any inserted word starts with a prefix.

Why this is worth learning

A path records a prefix; an end marker records membership of a complete word. Keeping those two facts separate makes insertion, exact search, and prefix search small operations with different stopping conditions.

Before coding: one-minute experiment

After Insert("apple"), what are Search("app"), StartsWith("app"), and Search("apple")? What changes after Insert("app")?

Function signature

type Trie struct { ... }
func Constructor() Trie
func (t *Trie) Insert(word string)
func (t *Trie) Search(word string) bool
func (t *Trie) StartsWith(prefix string) bool

Inputs / outputs

word: lowercase English word to insert or search.
prefix: lowercase English prefix to test.
Return: Search returns true only for complete inserted words; StartsWith returns true for any existing prefix path.

Example

Insert("apple")
Search("apple")   -> true
Search("app")     -> false
StartsWith("app") -> true
Insert("app")
Search("app")     -> true

Constraints

Words contain lowercase English letters.
Total inserted/search characters can be large, so operations should be linear in word length.

Core idea (near-solution)

A hash set supports exact membership directly, but repeated prefix queries require scanning words or adding a prefix index. A trie represents that index as shared character edges. Reaching a node means its prefix path exists; a separate end flag records whether that exact word was inserted. Without the flag, inserting apple would falsely insert app as well. Only insertion creates edges or sets end flags. Search and StartsWith walk existing paths without mutating them; the former additionally requires an end marker after consuming all letters.

Invariant: after processing the first i characters of a word, the current node represents exactly that prefix.

Algorithm (step-by-step)

Start at the root node.
During Insert, follow each character, creating a child only when absent. During queries, an absent child returns false without creating anything.
After the final character in Insert, mark the node as terminal.
For Search, traverse every character and return true only if the final node is terminal.
For StartsWith, traverse every character and return true if the path exists.

Correctness sketch

After consuming i bytes, the current node represents exactly the length-i prefix. Insertion follows existing edges or creates the missing next edge, preserving that path invariant and marking only the final node terminal. It never removes edges or terminals, so earlier words remain present. Search fails exactly when a required edge is absent; after all bytes, it succeeds only if the terminal marker is set. StartsWith uses the same walk but does not require a terminal marker. Thus inserting a longer word implies its prefixes have paths, not that they were inserted as words.

Trace (hand walkthrough)

Trace Walkthrough

Insert app: root -> a -> p -> p(end)
Insert apple: root -> a -> p -> p(end) -> l -> e(end)
Search app: path exists and final p is terminal -> true
StartsWith appl: path exists through l -> true
Search appl: path exists but l is not terminal -> false

Pitfalls to avoid

Returning true for Search("app") after inserting only apple.
Forgetting to initialize child maps or arrays.
Treating the root as a word unless empty words are explicitly supported.

Debugging lens

Test a word that is a prefix of another in both insertion orders, repeated insertion, and two independent constructors. A zero-value Trie is not the initialized object; use Constructor.

Complexity

Time: O(L) per operation, where L is word or prefix length.
Extra space: O(total characters inserted).

Implementation notes (Go)

A [26]*node array is fast and simple for lowercase English letters.
Methods should use pointer receivers so mutations affect the trie.

Contract precision

The fixed 26-child representation supports lowercase ASCII letters. Empty insertion marks the root terminal; Search("") then succeeds. StartsWith("") is true even before insertion because the empty path exists. Queries are read-only. Supporting Unicode would require a different alphabet representation.

Reconstruction checkpoint

Insert "sea" and "seal", then search "se", "sea", and prefix "se". Now suppose exact Search("se") accidentally sets an end flag. Which later observation exposes the mutation?

Model answer

The results must be false, true, and true. Repeating Search("se") must still be false; if it becomes true, a read operation changed membership. The node for sea remains terminal even though it has child l. Queries traverse existing edges and never create children or terminal flags.

Return to Trie · Module quiz

package solution

// Learner exercise scaffold; intentionally unsolved.
// The reference solution is the complete, separately tested answer.
// Reconstruction checkpoint:
// Insert "sea" and "seal", then search "se", "sea", and prefix "se". Now suppose exact
// Search("se") accidentally sets an end flag. Which later observation exposes the mutation?

// Trie stores lowercase English words by shared prefix paths.
type Trie struct {
	// Exercise step: add root node.
}

// Constructor initializes an empty trie.
func Constructor() Trie {
	return Trie{}
}

// Insert adds word to the trie.
func (t *Trie) Insert(word string) {
	// Exercise step: create missing prefix nodes and mark the final node as a word.
}

// Search reports whether word was inserted exactly.
func (t *Trie) Search(word string) bool {
	// Exercise step: traverse the path and check the terminal marker.
	return false
}

// StartsWith reports whether the prefix path exists; the empty root path always exists.
func (t *Trie) StartsWith(prefix string) bool {
	// Exercise step: traverse only the prefix path.
	return false
}

package solution

// Trie stores lowercase English words by shared prefix paths.
type Trie struct {
	// Exercise step: add root node.
}

// Constructor initializes an empty trie.
func Constructor() Trie {
	return Trie{}
}

// Insert adds word to the trie.
func (t *Trie) Insert(word string) {
	// Exercise step: create missing prefix nodes and mark the final node as a word.
}

// Search reports whether word was inserted exactly.
func (t *Trie) Search(word string) bool {
	// Exercise step: traverse the path and check the terminal marker.
	return false
}

Auto-advance

Run tests to see results

No issues detected