46:"/_next/static/chunks/33yus346z0l_n.js" 47:"/_next/static/chunks/2j22cxchii_xx.js" 48:"/_next/static/chunks/0iv56yrji_20j.js" 49:"/_next/static/chunks/32izpn90gvm22.js" 4a:"/_next/static/chunks/3j8bi-zu9bqs4.js" 4b:"/_next/static/chunks/1z-pox7hqp2x3.js" 4c:"/_next/static/chunks/20w4eaqlekefm.js" 4d:"/_next/static/chunks/1tn-0fivsxsv1.js" 4e:"/_next/static/chunks/09nq57stwzkgf.js" 4f:"/_next/static/chunks/3m1xjj5kw5fie.js" 50:"/_next/static/chunks/0gafyzg9j9yqj.js" 51:"/_next/static/chunks/3k2gyg36fnag_.js" 52:"/_next/static/chunks/3bgoyiso1rhn7.js" 53:"/_next/static/chunks/3cstd6xzfli_o.js" 54:"/_next/static/chunks/253gnmj0-cj17.js" 55:"/_next/static/chunks/0hlb44ca7-4a2.js" 56:"/_next/static/chunks/20329i6m_04t6.js" 57:"/_next/static/chunks/40mq7ggq-ozo4.js" 58:"/_next/static/chunks/082jo-0ajazgr.js" 59:"/_next/static/chunks/2ozcrjb_hh74t.js" 5a:"/_next/static/chunks/01a-3hvnqu8wl.js" 5b:"/_next/static/chunks/05i8en-x14ibi.js" 5c:"/_next/static/chunks/3m0r7x0jt5wm7.js" 5d:"/_next/static/chunks/2k8pepwc4pxns.js" 5e:"/_next/static/chunks/0wa9m1-tphf9u.js" 5f:"/_next/static/chunks/30jdm3dwz834g.js" 60:"/_next/static/chunks/0k9bl6dipnsvu.js" 61:"/_next/static/chunks/18ggtgz2yf759.js" 62:"/_next/static/chunks/0i3-eynrkvqi7.js" 63:I[593304,["$2b","$2c","$2d","$2e","$2f","$30","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61","$62"],"OwnedHydration"] 64:T4a7,To truly understand trie insertion, we must first internalize the **fundamental trie invariant**: > **Every path from the root to an end-of-word marker represents exactly one string in the trie.** This invariant is the lens through which all trie operations should be viewed. When we insert a string, we are not *storing* the string in the conventional sense—we are **creating a path** that encodes the string through the sequence of edges traversed. ### The Path Metaphor Imagine walking through a forest of infinite possibilities. Starting at the root (the forest entrance), each step you take is determined by the next character in your string. If a path exists for that character, you follow it. If no path exists, you carve a new one—creating a new node and establishing a new edge. When you've consumed all characters in your string, you plant a flag at your current position: the **end-of-word marker**. This flag says, *"A complete string ends here."* Without this marker, we couldn't distinguish between strings that are prefixes of other strings. For example, we need to differentiate between having inserted just "cat" versus having inserted both "cat" and "catastrophe".65:T464,class TrieNode { children: (TrieNode | null)[]; isEndOfWord: boolean; constructor() { // 26 slots for 'a' through 'z' this.children = new Array(26).fill(null); this.isEndOfWord = false; } } class Trie { private root: TrieNode; constructor() { this.root = new TrieNode(); } /** * Inserts a word into the trie. * Time: O(m) where m is the length of the word * Space: O(m * 26) in worst case for all new nodes */ insert(word: string): void { let current = this.root; for (const char of word) { // Map 'a'-'z' to indices 0-25 const index = char.charCodeAt(0) - 'a'.charCodeAt(0); // Create node if it doesn't exist if (current.children[index] === null) { current.children[index] = new TrieNode(); } // Move to the child current = current.children[index]!; } // Mark the end of the word current.isEndOfWord = true; } }66:T47a,### Space Complexity: O(m) per Insert (Worst Case) In the worst case, no prefix of the new word exists in the trie, so we create `m` new nodes. The space for each node depends on the implementation: **Array-based (alphabet size Σ):** - Each node: O(Σ) space for child pointers - Worst-case insert: O(m × Σ) total space - For 26-letter alphabet: O(26m) = O(m) **Hash map-based:** - Each node: O(1) space initially (empty map) - Maps grow only as children are added - Worst-case insert: O(m) for nodes, plus hash map overhead ### Aggregate Space for n Insertions If we insert `n` strings with total combined length `L` (sum of all string lengths), the trie uses at most O(L) nodes (each character in all strings could require its own node in the worst case). In practice, prefix sharing means actual node count is often much less than L. **Best case (maximum sharing):** If all strings are permutations of each other or highly overlapping prefixes, node count approaches the size of the longest string. **Worst case (no sharing):** All strings are unique from the first character (e.g., "apple", "banana", "cherry"). Node count equals L.67:T485,class TrieNode { children: Map; count: number; // 0 if not a complete word, >0 for word count constructor() { this.children = new Map(); this.count = 0; } } class FrequencyTrie { private root: TrieNode; constructor() { this.root = new TrieNode(); } /** * Insert a word and increment its frequency. */ insert(word: string): void { let current = this.root; for (const char of word) { if (!current.children.has(char)) { current.children.set(char, new TrieNode()); } current = current.children.get(char)!; } current.count++; // Increment, don't just set to 1 } /** * Get the frequency of a word (0 if not present). */ getFrequency(word: string): number { let current = this.root; for (const char of word) { if (!current.children.has(char)) { return 0; } current = current.children.get(char)!; } return current.count; } }68:T535,class TrieNode { children: Map; isEndOfWord: boolean; prefixCount: number; // How many words pass through this node constructor() { this.children = new Map(); this.isEndOfWord = false; this.prefixCount = 0; } } class PrefixCountTrie { private root: TrieNode; constructor() { this.root = new TrieNode(); } /** * Insert and update prefix counts along the path. */ insert(word: string): void { let current = this.root; for (const char of word) { if (!current.children.has(char)) { current.children.set(char, new TrieNode()); } current = current.children.get(char)!; current.prefixCount++; // Increment at each node along path } current.isEndOfWord = true; } /** * Count words that start with the given prefix. * O(m) where m is prefix length. */ countWordsWithPrefix(prefix: string): number { let current = this.root; for (const char of prefix) { if (!current.children.has(char)) { return 0; } current = current.children.get(char)!; } return current.prefixCount; } }44:["$","$L63",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792304303588,"state":{"data":{"json":{"id":"seed_320f7171c94622c8fcae5e7a01573636","slug":"trie-operations-insert-search-startswith","category":"Data Structures & Algorithms","topic":"Trie Operations — Insert, Search, StartsWith","title":"Trie Operations — Insert, Search, StartsWith","description":"Master the three fundamental trie operations: inserting strings character by character, searching for exact matches, and finding prefix matches. Understand the O(m) time complexity and implementation patterns that make tries powerful.","difficulty":"INTERMEDIATE","estimatedMinutes":60,"pages":[{"id":"seed_a56f26833054c4880191b47698c30751","title":"Insert — Create Path for Each Character","order":0,"content":[{"id":"opening-hook","title":"Building Strings One Character at a Time","content":[{"data":{"content":"The **insert** operation is the foundational building block of every trie. Without insertion, there is no trie—just an empty root node waiting to be populated. Yet the elegance of trie insertion lies not in complexity, but in its beautiful simplicity: we trace a path through the tree, character by character, creating new nodes only when necessary.\n\nUnlike hash tables that compute a hash and store the entire string at once, or binary search trees that compare whole strings at each node, a trie constructs a **character-level path** from root to a termination marker. This architectural decision has profound implications for prefix-based operations, memory sharing, and lexicographic ordering—advantages we explored in previous modules.\n\nIn this page, we will dissect the insert operation with surgical precision. You'll understand not just *how* to implement it, but *why* each step exists, *what* invariants must be maintained, and *when* different implementation choices affect performance."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Master","content":"By the end of this page, you will be able to: (1) Explain the conceptual model of trie insertion and why it differs from other data structures, (2) Implement insertion for both array-based and hash map-based trie nodes, (3) Trace through insertions step-by-step, visualizing the tree structure, (4) Analyze the time and space complexity with rigorous justification, and (5) Handle edge cases including empty strings, duplicate insertions, and special characters.","variant":"info"},"type":"callout"}]},{"id":"conceptual-model","title":"The Conceptual Model: Paths as Strings","content":[{"data":{"content":"$64"},"type":"text"},{"data":{"icon":"Lightbulb","title":"Why End-of-Word Markers Are Non-Negotiable","content":"Consider inserting \"app\" and \"apple\" into a trie. Both share the path a→p→p. Without an end-of-word marker at the node reached after processing \"app\", we'd have no way to know that \"app\" is a valid word—we'd only see it as a prefix of \"apple\". The marker transforms a path from being a \"prefix observation\" into a \"complete string declaration\".","variant":"tip"},"type":"callout"},{"data":{"content":"### Structural Consequences\n\nThis path-based representation has several structural consequences that shape the insert algorithm:\n\n1. **Root is never a character:** The root node is a sentinel—an entry point that doesn't correspond to any character. The first character of every string labels the edge *from* the root to its first child.\n\n2. **Shared prefixes share nodes:** If we insert \"team\" and \"tear\", the nodes for 't', 'e', and 'a' are shared. The paths diverge only at the fourth character ('m' vs 'r'). This prefix sharing is automatic—a natural consequence of following existing paths.\n\n3. **Depth equals string length:** A string of length `m` creates a path of exactly `m` nodes below the root. The end-of-word marker is placed at depth `m`.\n\n4. **Character set determines branching factor:** Each node can have as many children as there are characters in the alphabet. For lowercase English, that's 26 potential children per node—though most nodes will have far fewer."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"algorithm-step-by-step","title":"The Insertion Algorithm: Step-by-Step","content":[{"data":{"content":"Let's formalize the insertion process with a rigorous, step-by-step algorithm. We'll then trace through concrete examples to cement understanding.\n\n### The Algorithm\n\nGiven a trie with root node `root` and a string `word` to insert:"},"type":"text"},{"data":{"type":"ordered","items":["**Initialize current pointer:** Set `current = root`. This pointer will walk down the trie as we process each character.","**Iterate through each character:** For each character `c` in `word` (from first to last):","**Check if child exists:** Look for a child of `current` corresponding to character `c`.","**If child doesn't exist, create it:** Allocate a new TrieNode and add it as the child of `current` for character `c`.","**Advance the pointer:** Move `current` to the child node corresponding to `c` (whether it existed or was just created).","**Mark end of word:** After processing all characters, set `current.isEndOfWord = true`."],"title":{"icon":"ListIcon","text":"Insert Algorithm Steps","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"### Why Each Step Matters\n\n**Step 1 (Initialize):** We must start at the root because every string path begins there. The root is the universal prefix—the empty string \"\" that prefixes all strings.\n\n**Steps 2-5 (Character Loop):** This is the core of the algorithm. We're essentially doing a multi-level lookup/create operation. For each character, we either follow an existing edge (the character was seen before in some prefix) or create a new edge (this character at this position is new to the trie).\n\n**Step 6 (Mark End):** This final step is often overlooked but is absolutely critical. Without it, we're just creating paths in the trie without declaring which paths represent complete strings. The end-of-word marker is the semantic payload that transforms a structural path into a meaningful dictionary entry."},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Most Common Bug","content":"Forgetting to set the end-of-word marker is the #1 bug in trie implementations. Your insert will appear to work—the nodes are created—but search and startsWith will fail for some queries because the trie doesn't know which paths are complete words versus mere prefixes.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"traced-example","title":"Traced Example: Building a Trie Word by Word","content":[{"data":{"content":"Let's trace through inserting multiple words to see how the trie evolves. We'll insert, in order: **\"cat\"**, **\"car\"**, **\"card\"**, **\"care\"**, **\"careful\"**.\n\n### Initial State\n\nWe start with just the root node—an empty trie:\n\n```\nroot [isEndOfWord: false]\n└── (no children)\n```\n\n### After Inserting \"cat\"\n\nProcessing characters: **c → a → t**\n\n- `c`: No child at root for 'c'. Create node. Move to it.\n- `a`: No child for 'a'. Create node. Move to it.\n- `t`: No child for 't'. Create node. Move to it.\n- Mark `isEndOfWord = true`.\n\n```\nroot\n└── c\n └── a\n └── t [END]\n```"},"type":"text"},{"data":{"content":"### After Inserting \"car\"\n\nProcessing: **c → a → r**\n\n- `c`: Child exists at root! Follow it.\n- `a`: Child exists! Follow it.\n- `r`: No child for 'r'. Create node. Move to it.\n- Mark `isEndOfWord = true`.\n\n```\nroot\n└── c\n └── a\n ├── t [END]\n └── r [END]\n```\n\n**Notice:** We reused the existing path for \"ca\". Only 'r' required a new node. This is prefix sharing in action.\n\n### After Inserting \"card\"\n\nProcessing: **c → a → r → d**\n\n- `c`: Follow existing.\n- `a`: Follow existing.\n- `r`: Follow existing (we created it for \"car\").\n- `d`: No child for 'd'. Create node. Move to it.\n- Mark `isEndOfWord = true`.\n\n```\nroot\n└── c\n └── a\n ├── t [END]\n └── r [END]\n └── d [END]\n```\n\n**Key Insight:** \"car\" is now both a complete word AND a prefix of \"card\". Both 'r' node and 'd' node have `isEndOfWord = true`."},"type":"text"},{"data":{"content":"### After Inserting \"care\" and \"careful\"\n\n**\"care\":** c(follow) → a(follow) → r(follow) → e(create) → mark END\n\n**\"careful\":** c → a → r → e(follow!) → f(create) → u(create) → l(create) → mark END\n\nFinal structure:\n\n```\nroot\n└── c\n └── a\n ├── t [END]\n └── r [END]\n ├── d [END]\n └── e [END]\n └── f\n └── u\n └── l [END]\n```\n\n### Observations from the Trace\n\n1. **Five words, but the total node count is small** thanks to shared prefixes (c-a is shared by all, c-a-r is shared by car/card/care/careful).\n\n2. **Multiple words can share the same node:** The 'r' node is part of four different word paths.\n\n3. **Some nodes have isEndOfWord=true even with children:** The 'r' node marks the end of \"car\" but also has children 'd' and 'e'. This is perfectly normal.\n\n4. **Insertion order doesn't matter for final structure:** Whether we insert \"careful\" before \"care\" or after, the trie structure is the same."},"type":"text"},{"data":{"icon":"Info","title":"Insertion Order Independence","content":"Unlike binary search trees where insertion order dramatically affects shape, trie structure is determined solely by the set of strings inserted, not the order. This property simplifies reasoning about trie behavior and means you never need to \"balance\" a trie.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"implementation-patterns","title":"Implementation Patterns: Array vs. Hash Map Children","content":[{"data":{"content":"The insert algorithm is the same regardless of how we represent children, but the implementation details differ. Let's examine both the array-based and hash map-based approaches, understanding the trade-offs that inform our choice.\n\n### Array-Based Children (Fixed Alphabet)\n\nWhen the alphabet is fixed and small (e.g., 26 lowercase letters), we can use an array of child pointers:"},"type":"text"},{"data":{"code":"$65","fileName":"trie-insert-array.ts","languages":[{"label":"TypeScript","value":"typescript"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"**Array Approach Analysis:**\n\n- **Lookup speed:** O(1) to find a child—just compute the index and access the array.\n- **Memory per node:** 26 pointers (or 26 × 8 = 208 bytes for 64-bit pointers, plus overhead).\n- **Best for:** Known, small alphabets where most characters are used.\n- **Weakness:** Wastes memory when alphabet is large or sparsely used.\n\n### Hash Map-Based Children (Flexible Alphabet)"},"type":"text"},{"data":{"code":"class TrieNode {\n children: Map;\n isEndOfWord: boolean;\n \n constructor() {\n this.children = new Map();\n this.isEndOfWord = false;\n }\n}\n\nclass Trie {\n private root: TrieNode;\n \n constructor() {\n this.root = new TrieNode();\n }\n \n /**\n * Inserts a word into the trie.\n * Time: O(m) where m is the length of the word\n * Space: O(m) for new nodes (each node only stores actual children)\n */\n insert(word: string): void {\n let current = this.root;\n \n for (const char of word) {\n // Check if child exists, create if not\n if (!current.children.has(char)) {\n current.children.set(char, new TrieNode());\n }\n \n // Move to the child\n current = current.children.get(char)!;\n }\n \n // Mark the end of the word\n current.isEndOfWord = true;\n }\n}","fileName":"trie-insert-hashmap.ts","languages":[{"label":"TypeScript","value":"typescript"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"**Hash Map Approach Analysis:**\n\n- **Lookup speed:** O(1) average, but with hash computation overhead.\n- **Memory per node:** Only stores children that actually exist. Far more memory-efficient for sparse tries or large alphabets.\n- **Best for:** Unicode strings, mixed-case, special characters, or any situation where alphabet is unbounded.\n- **Weakness:** Slightly slower due to hashing; less cache-friendly."},"type":"text"},{"data":{"rows":[["Lookup Speed","O(1) with simple arithmetic","O(1) average with hash overhead"],["Memory Efficiency","Wastes space for sparse nodes","Only stores actual children"],["Best Alphabet Size","Small, fixed (26-128)","Large, variable (Unicode)"],["Implementation Complexity","Simpler index math","Slightly more code"],["Cache Locality","Better (contiguous array)","Worse (hash buckets)"]],"caption":"Array vs. Hash Map Children: Trade-offs","headers":["Criterion","Array-Based","Hash Map-Based"]},"type":"table"}],"titleType":"number","titleNumber":4},{"id":"time-space-complexity","title":"Time and Space Complexity Analysis","content":[{"data":{"content":"Let's rigorously analyze the complexity of the insert operation. Understanding these bounds is essential for making informed data structure choices.\n\n### Time Complexity: O(m)\n\n**Where `m` is the length of the string being inserted.**\n\nThe algorithm iterates through each character exactly once. At each character, we perform:\n\n1. **Child lookup:** O(1) for both array (index computation) and hash map (amortized hash lookup).\n2. **Potential node creation:** O(1) for object allocation.\n3. **Pointer update:** O(1).\n\nSince we do O(1) work for each of `m` characters, total time is **O(m)**.\n\n**Crucially, this is independent of the number of strings already in the trie.** Whether the trie contains 10 words or 10 million words, inserting a string of length `m` always takes O(m) time. This is a remarkable property that hash tables share for insertion, but balanced BSTs do not (their O(log n) factor depends on total elements)."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Comparing to Alternatives","content":"Hash set insert: O(m) to hash + O(1) to store = O(m). Similar to trie! But tries give you prefix operations. Balanced BST with string keys: O(m log n) because each comparison takes O(m) and there are O(log n) comparisons. Tries win when you need prefix matching or have many strings with shared prefixes.","variant":"tip"},"type":"callout"},{"data":{"content":"$66"},"type":"text"},{"data":{"rows":[["Time (single insert)","O(m)","m = length of string being inserted"],["Space (single insert, worst)","O(m)","When no prefix exists in trie"],["Space (single insert, best)","O(1)","When entire string is already a prefix of existing word"],["Aggregate time (n inserts)","O(L)","L = total characters across all strings"],["Aggregate space (n inserts)","O(L × Σ) array / O(L) hash","Σ = alphabet size"]],"caption":"Insert Complexity Summary","headers":["Metric","Complexity","Notes"]},"type":"table"}],"titleType":"number","titleNumber":5},{"id":"edge-cases-robustness","title":"Edge Cases and Robustness Considerations","content":[{"data":{"content":"Production-quality code must handle edge cases gracefully. Let's examine the scenarios that trip up naive implementations.\n\n### Edge Case 1: Empty String\n\nWhat happens if we insert an empty string `\"\"`?\n\n**Algorithm behavior:** The character loop executes zero times. We immediately mark `root.isEndOfWord = true`.\n\n**Is this correct?** Depends on your requirements. If empty strings should be valid dictionary entries, this is correct. If not, guard against it:\n\n```typescript\ninsert(word: string): void {\n if (word.length === 0) {\n return; // or throw, depending on API contract\n }\n // ... rest of insertion\n}\n```\n\n**Implication:** If you allow empty string insertion, `search(\"\")` should return true, and `startsWith(\"\")` should always return true (every string starts with the empty prefix)."},"type":"text"},{"data":{"content":"### Edge Case 2: Duplicate Insertions\n\nWhat if we insert the same word twice?\n\n**Algorithm behavior:** The second insertion follows the existing path (no new nodes needed) and sets `isEndOfWord = true` again on a node that's already marked.\n\n**Result:** The trie is unchanged. Insertion is idempotent.\n\n**Performance implication:** Duplicate insertions are actually *faster* than new insertions because no memory allocation occurs. This makes tries excellent for building dictionaries from potentially duplicated input (e.g., word counts from text)."},"type":"text"},{"data":{"content":"### Edge Case 3: Prefix is Already a Word\n\nInsert \"apple\", then insert \"app\".\n\n**Algorithm behavior:** When inserting \"app\", we follow existing nodes for a→p→p. The 'p' node (at depth 3) is already created as part of \"apple's\" path. We simply mark this node as `isEndOfWord = true`.\n\n**Result:** Both \"apple\" and \"app\" are now valid words. The node for the third 'p' has:\n- `isEndOfWord = true` (because \"app\" ends here)\n- A child 'l' (because \"apple\" continues)\n\nThis demonstrates that **any node can be both a word termination and a prefix node**."},"type":"text"},{"data":{"content":"### Edge Case 4: Word is Already a Prefix\n\nInsert \"app\", then insert \"apple\".\n\n**Algorithm behavior:** When inserting \"apple\", we follow existing nodes for a→p→p. After that, we create new nodes for l→e and mark 'e' as end of word.\n\n**Result:** Same trie structure as Case 3. Insertion order doesn't affect final structure."},"type":"text"},{"data":{"icon":"AlertCircle","title":"Character Validation","content":"For array-based tries with a fixed alphabet, inserting characters outside that alphabet causes bugs (array index out of bounds or negative indices). Always validate input or use hash map-based children for untrusted input. Example: inserting \"café\" into a lowercase-only trie crashes on 'é' unless handled.","variant":"warning"},"type":"callout"},{"data":{"code":"/**\n * Robust insert with input validation\n */\ninsert(word: string): void {\n // Handle empty string based on requirements\n if (word.length === 0) {\n return; // Silently ignore; alternatively throw\n }\n \n let current = this.root;\n \n for (const char of word) {\n // Validate character is in expected range\n const index = char.charCodeAt(0) - 'a'.charCodeAt(0);\n if (index < 0 || index >= 26) {\n throw new Error(`Invalid character '${char}' - only lowercase a-z allowed`);\n }\n \n if (current.children[index] === null) {\n current.children[index] = new TrieNode();\n }\n \n current = current.children[index]!;\n }\n \n current.isEndOfWord = true;\n}","fileName":"trie-insert-robust.ts","languages":[{"label":"TypeScript","value":"typescript"}],"showLineNumbers":true},"type":"code"}],"titleType":"number","titleNumber":6},{"id":"common-variations","title":"Common Variations on Insert","content":[{"data":{"content":"The basic insert operation can be extended to support additional functionality. Here are variations you'll encounter in practice.\n\n### Variation 1: Storing Values (Trie as a Map)\n\nInstead of just marking end-of-word, store an associated value. This transforms the trie from a set into a map."},"type":"text"},{"data":{"code":"class TrieNode {\n children: Map>;\n value: T | null; // null if no value at this node\n \n constructor() {\n this.children = new Map();\n this.value = null;\n }\n}\n\nclass TrieMap {\n private root: TrieNode;\n \n constructor() {\n this.root = new TrieNode();\n }\n \n /**\n * Insert a key-value pair into the trie.\n * Returns the previous value if key existed, null otherwise.\n */\n insert(key: string, value: T): T | null {\n let current = this.root;\n \n for (const char of key) {\n if (!current.children.has(char)) {\n current.children.set(char, new TrieNode());\n }\n current = current.children.get(char)!;\n }\n \n const previousValue = current.value;\n current.value = value;\n return previousValue;\n }\n}","fileName":"trie-map-insert.ts","languages":[{"label":"TypeScript","value":"typescript"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"### Variation 2: Counting Words (Frequency)\n\nTrack how many times each word has been inserted. Useful for autocomplete ranking."},"type":"text"},{"data":{"code":"$67","fileName":"trie-frequency.ts","languages":[{"label":"TypeScript","value":"typescript"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"### Variation 3: Prefix Count (Subtree Statistics)\n\nTrack how many words pass through each node. Enables efficient prefix counting."},"type":"text"},{"data":{"code":"$68","fileName":"trie-prefix-count.ts","languages":[{"label":"TypeScript","value":"typescript"}],"showLineNumbers":true},"type":"code"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary: Mastering Trie Insertion","content":[{"data":{"content":"We've thoroughly explored the trie insert operation—from conceptual model to implementation details to edge cases. Let's consolidate the key takeaways:"},"type":"text"},{"data":{"type":"ordered","items":["**Insert creates a character-by-character path** from root to an end-of-word marker. Each edge represents a character.","**Prefix sharing is automatic:** When strings share prefixes, they share nodes. No special coding required.","**The end-of-word marker is critical:** Without it, we can't distinguish complete words from mere prefixes.","**Time complexity is O(m):** Independent of how many strings are already in the trie. This is optimal for string insertion.","**Space complexity is O(m) worst-case per insert:** When no prefix exists. With sharing, aggregate space can be much better.","**Array vs. hash map children** is a memory-speed tradeoff. Arrays for small, fixed alphabets; hash maps for flexibility.","**Handle edge cases:** Empty strings, duplicates, and character validation require explicit decisions.","**Variations extend functionality:** Values, frequencies, and prefix counts are common enhancements."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nNow that we can build tries through insertion, we need to query them. The next page explores the **search** operation—how to determine if a complete word exists in the trie. We'll see how search follows the same path-walking logic as insert, but with different termination conditions."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now have a comprehensive understanding of trie insertion. You can implement it with either array or hash map children, analyze its complexity, handle edge cases, and extend it for advanced use cases like frequency counting and prefix statistics. Next: searching for exact matches.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_66b19b593c536e418148af6f119a5a14","title":"Search — Follow Path, Check End-of-Word","order":1,"content":null,"isLocked":true},{"id":"seed_727ebe23b0b29ca525cfb537cd57634f","title":"StartsWith — Follow Path, Don't Require End-of-Word","order":2,"content":null,"isLocked":true},{"id":"seed_fa1aa33215d807e06a281d7a02f6b04a","title":"Time Complexity — O(m) Where m Is String Length","order":3,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792304303587,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"trie-operations-insert-search-startswith"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"trie-operations-insert-search-startswith\"},\"type\":\"query\"}]"},{"dehydratedAt":1792304303588,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792304303586,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_320f7171c94622c8fcae5e7a01573636"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_320f7171c94622c8fcae5e7a01573636\"},\"type\":\"query\"}]"},{"dehydratedAt":1792304303588,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792304303586,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_66b19b593c536e418148af6f119a5a14"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_66b19b593c536e418148af6f119a5a14\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792304303588,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792304303586,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_66b19b593c536e418148af6f119a5a14"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_66b19b593c536e418148af6f119a5a14\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792304303588,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792304303586,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_66b19b593c536e418148af6f119a5a14"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_66b19b593c536e418148af6f119a5a14\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792304303588,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_66b19b593c536e418148af6f119a5a14","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_66b19b593c536e418148af6f119a5a14\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@69"}]},"children":"$L6a"}]