Implement Trie (Prefix Tree)

Design a trie that supports insertion, full-word search, and prefix search.

Function signature

type Trie struct { /* fields */ }

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

• Insert(word): add a word to the trie.
• Search(word): return true if the exact word exists.
• StartsWith(prefix): return true if any word starts with the prefix.

Example

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

Constraints

• 0 <= number of operations <= 100_000
• words are lowercase a-z

Core idea (near-solution)

Each node stores up to 26 children and a boolean isWord. Insert walks/creates nodes; Search and StartsWith walk and check the end flag as needed.

Invariant: a path from root spells a prefix; isWord marks complete words.

Algorithm (step-by-step)

• Insert: for each character, move/create child; mark final node as word.
• Search: walk characters; return true if path exists and final node is word.
• StartsWith: walk characters; return true if path exists.

Correctness sketch

• Invariant: a path from root spells a prefix; isWord marks complete words.
• Each node represents a prefix; inserting builds all prefixes for a word.
• Searching follows the unique path for the word/prefix.
• Wildcards branch over all possible children, covering all matches.

Trace (hand walkthrough)

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

Walk:
- Insert "apple": create path a->p->p->l->e, mark e as word
- Search "apple" -> path exists and isWord true
- Search "app" -> path exists but isWord false
- Insert "app" then Search "app" -> true

Pitfalls to avoid

• Forgetting to mark isWord on insert.
• Treating a prefix as a full word in Search.
• Re-creating nodes instead of reusing existing children.

Complexity

• Each operation: O(L) where L is word length.
• Space: O(total characters).

Implementation notes (Go)

• Use [26]*Node children for constant-time branching.
• Convert ch - 'a' to index; inputs are lowercase a-z.