Trie Insert Operation in DSA Typescript

Mental Model

A trie stores words by branching out letters step by step, creating paths for each word.

Analogy: Imagine a tree where each branch is a letter, and walking down branches spells out words like walking down streets to reach houses.

root
 ↓
[ ]
Each box [] is a node that can lead to next letters.

Dry Run Walkthrough

Input: Insert words: "cat", then "car" into an empty trie

Goal: Build a trie that stores both words sharing common prefix 'ca'

Step 1: Insert 'c' as child of root

root -> [c]
[c] -> null

Why: Start the path for the first word with its first letter

Step 2: Insert 'a' as child of 'c'

root -> [c] -> [a]
[a] -> null

Why: Continue the path for the first word with second letter

Step 3: Insert 't' as child of 'a' and mark end of word

root -> [c] -> [a] -> [t*]
[t*] -> null

Why: Complete the first word by adding last letter and marking word end

Step 4: Insert 'r' as sibling of 't' under 'a' for second word

root -> [c] -> [a] -> [t*]
                   -> [r*]
[t*], [r*] marked end of words

Why: Add second word sharing prefix 'ca' but different last letter

Result:

root -> [c] -> [a] -> [t*]
                   -> [r*]
*t and *r mark ends of words 'cat' and 'car'

Annotated Code

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!; // advance to child node
    }
    node.isEndOfWord = true; // mark end of word
  }

  print(node: TrieNode = this.root, prefix: string = ''): void {
    if (node.isEndOfWord) {
      console.log(prefix);
    }
    for (const [char, child] of node.children) {
      this.print(child, prefix + char);
    }
  }
}

const trie = new Trie();
trie.insert('cat');
trie.insert('car');
trie.print();

if (!node.children.has(char)) { node.children.set(char, new TrieNode()); }

create new child node if letter path does not exist

node = node.children.get(char)!;

advance current node to child node for next letter

node.isEndOfWord = true;

mark current node as end of a complete word

Output

cat

car

Complexity Analysis

Time: O(m) because we process each of the m letters in the word once

Space: O(m) in worst case when all letters are new and need new nodes

vs Alternative: Compared to storing words in a list, trie insert is faster for prefix searches but uses more space for nodes

Edge Cases

Inserting empty string

Marks root as end of word, representing empty word

DSA Typescript

node.isEndOfWord = true;

Inserting word that is prefix of existing word (e.g., insert 'ca' after 'cat')

Marks node at 'a' as end of word without adding new nodes

DSA Typescript

node.isEndOfWord = true;

Inserting duplicate word

No new nodes created, just marks end of word again

DSA Typescript

if (!node.children.has(char)) { ... }

When to Use This Pattern

When you need to store many words and quickly find if a prefix or word exists, use a trie insert pattern to build the structure efficiently.

Common Mistakes

Mistake: Not marking the end of word node, so words are not recognized as complete
Fix: Always set isEndOfWord = true after inserting all letters of a word

Mistake: Creating new nodes even if the letter path already exists
Fix: Check if child node exists before creating new node to avoid duplicates

Summary

Inserts words letter by letter into a tree-like structure sharing prefixes.

Use when you want fast prefix-based word storage and lookup.

The key is to create nodes only when needed and mark the end of each word.