Tries

LeetCode 208

LeetCode #208Difficulty: MediumNeetCode 150

LeetCode 208: Implement Trie (Prefix Tree)

LeetCode

Implement a trie with insert, search, and startsWith methods.

Problem Description

A trie (pronounced as 'try') or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings.

Examples:
Input: insert('apple'), search('apple'), startsWith('app')
Output: [true, true]
Constraints:
  • 1 <= word.length, prefix.length <= 2000

Core Mental Model

Each edge represents a character. Common prefixes share nodes down the hierarchy.

Formal Loop Invariant

Invariant: Node marked isEndOfWord terminates a valid inserted word.

Key Architectural Takeaway:

Tries enable O(L) prefix queries independent of the total number of words N in the dictionary.

Asymptotic Complexity Analysis

Time ComplexityO(L) per operationLinear scan
Space ComplexityO(Total characters inserted)Constant auxiliary

Bottleneck: Bounded by alphabet size.

Edge Cases & Screener Traps

  • Empty string
  • Searching word before insert