208. Implement Trie (Prefix Tree)

At a Glance

Topic: tries
Pattern: Trie
Difficulty: Medium
Companies: Amazon, Google, Meta, Microsoft, Bloomberg
Frequency: Very High
LeetCode: 208

Problem (one-liner)

Implement a prefix tree with insert(word), search(word) (full word exists), and startsWith(prefix) (any inserted word has that prefix).

Recognition Cues

Prefix / autocomplete core data structure
Each edge labeled by character; path from root spells token
Terminal flag marks completed dictionary words vs mere prefixes

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Hash set of words — search O(1) but startsWith scans all words — O(n * L) bad.
Trie — O(L) per op per word length L, alphabet-sized branching.

Optimal Solution

Go

package main

type Trie struct {
	children [26]*Trie
	isWord   bool
}

func Constructor() Trie {
	return Trie{}
}

func (trie *Trie) Insert(word string) {
	node := trie
	for index := range word {
		offset := int(word[index] - 'a')
		if node.children[offset] == nil {
			node.children[offset] = &Trie{}
		}
		node = node.children[offset]
	}
	node.isWord = true
}

func (trie *Trie) Search(word string) bool {
	node := trie.walk(word)
	return node != nil && node.isWord
}

func (trie *Trie) StartsWith(prefix string) bool {
	return trie.walk(prefix) != nil
}

func (trie *Trie) walk(prefix string) *Trie {
	node := trie
	for index := range prefix {
		offset := int(prefix[index] - 'a')
		if node.children[offset] == nil {
			return nil
		}
		node = node.children[offset]
	}
	return node
}

JavaScript

class Trie {
	constructor() {
		this.children = new Map();
		this.isWord = false;
	}

	insert(word) {
		let node = this;
		for (let index = 0; index < word.length; index++) {
			const letter = word[index];
			if (!node.children.has(letter)) {
				node.children.set(letter, new Trie());
			}
			node = node.children.get(letter);
		}
		node.isWord = true;
	}

	search(word) {
		const node = this.walk(word);
		return node !== null && node.isWord;
	}

	startsWith(prefix) {
		return this.walk(prefix) !== null;
	}

	walk(prefix) {
		let node = this;
		for (let index = 0; index < prefix.length; index++) {
			const letter = prefix[index];
			if (!node.children.has(letter)) {
				return null;
			}
			node = node.children.get(letter);
		}
		return node;
	}
}

Walkthrough

Insert "apple", then query:

op	trace
`insert("apple")`	create chain `a→p→p→l→e`, mark terminal at `e`
`search("app")`	walk succeeds but terminal false → `false`
`startsWith("app")`	walk succeeds → `true`

Invariant: every node along an inserted word exists; isWord distinguishes dictionary membership from prefix-only nodes.

Edge Cases

Empty string — define policy (usually allowed if tests include it)
Duplicate inserts — idempotent if terminal flag set again

Pitfalls

Forgetting isWord at terminal after walking full insert
Using search logic for startsWith without distinguishing terminal-only requirement

Variants

Unicode / arbitrary alphabet → map[rune]*Trie instead of fixed array.
Count words with prefix → store frequency at nodes.

Mind-Map Tags

#trie #prefix-tree #insert #search #startsWith