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.

Practice

1. What is the main purpose of the insert operation in a Trie data structure?

easy

A. To add a word character by character into the Trie

B. To delete a word from the Trie

C. To search for a word in the Trie

D. To count the number of words in the Trie

Solution

1. Step 1: Understand the insert operation

   The insert operation adds each character of a word into the Trie one by one, creating new nodes if needed.

2. Step 2: Differentiate from other operations

   Deleting removes words, searching finds words, counting totals words. Insert specifically adds words.

3. Final Answer:

   To add a word character by character into the Trie -> Option A

4. Quick Check:

   Insert = Add word [OK]

Hint: Insert means adding word step-by-step [OK]

Common Mistakes:

• Confusing insert with search or delete
• Thinking insert counts words
• Assuming insert replaces words

2. Which of the following is the correct TypeScript syntax to start inserting a word into a Trie node named root?

easy

A. let node = root;

B. node = root;

C. const node = root()

D. var node == root;

Solution

1. Step 1: Understand variable declaration in TypeScript

   Using let declares a variable that can be reassigned, suitable for traversal nodes.

2. Step 2: Check syntax correctness

   let node = root; uses correct assignment with let. node = root; misses declaration keyword. const node = root() wrongly calls root as a function. var node == root; uses invalid comparison operator.

3. Final Answer:

   let node = root; -> Option A

4. Quick Check:

   Correct variable declaration = let node = root; [OK]

Hint: Use let for variable assignment in TypeScript [OK]

Common Mistakes:

• Missing let or const keyword
• Using == instead of = for assignment
• Calling node as a function

3. Given the following TypeScript code snippet for inserting the word "cat" into an empty Trie, what will be the printed output after insertion?

class TrieNode {
  children: Map = new Map();
  isEndOfWord = false;
}

const root = new TrieNode();

function insert(word: string) {
  let node = root;
  for (const char of word) {
    if (!node.children.has(char)) {
      node.children.set(char, new TrieNode());
    }
    node = node.children.get(char)!;
  }
  node.isEndOfWord = true;
}

insert("cat");

console.log(Array.from(root.children.keys()));

medium

A. ["cat"]

B. ["c", "a", "t"]

C. []

D. ["c"]

Solution

1. Step 1: Trace insertion of "cat" into Trie

   Starting at root, 'c' is not present, so a new node for 'c' is created. Then move to 'c' node, 'a' is added as child, then 't' as child of 'a'.

2. Step 2: Check root's children keys

   Root only has one child node for 'c'. The keys of root.children are ['c'].

3. Final Answer:

   ["c"] -> Option D

4. Quick Check:

   Root children keys after insert = ["c"] [OK]

Hint: Root children keys show first letters only [OK]

Common Mistakes:

• Expecting all letters at root level
• Confusing keys with full words
• Ignoring Map keys method

4. Identify the error in the following TypeScript code snippet for inserting a word into a Trie:

function insert(word: string) {
  let node = root;
  for (const char of word) {
    if (!node.children.has(char)) {
      node.children.set(char, new TrieNode());
    }
    node = node.children.get(char);
  }
  node.isEndOfWord = true;
}

medium

A. Using 'let' instead of 'const' for node

B. Missing parentheses when creating new TrieNode

C. Not checking if node.children.get(char) is undefined

D. Not marking isEndOfWord as false initially

Solution

1. Step 1: Check new object creation syntax

   In TypeScript, when creating a new object, parentheses are required even if no arguments are passed. new TrieNode should be new TrieNode().

2. Step 2: Verify other parts

   Using 'let' for node is fine since node changes. The get method is safe here because we just set the key if missing. isEndOfWord is set at the end, initial value doesn't cause error.

3. Final Answer:

   Missing parentheses when creating new TrieNode -> Option B

4. Quick Check:

   new object needs () [OK]

Hint: Always use () when calling constructors [OK]

Common Mistakes:

• Omitting () after new keyword
• Confusing let and const for variables
• Ignoring possible undefined from get()

5. You want to insert multiple words ["bat", "ball", "batman"] into a Trie. After inserting all, which of the following statements is true about the Trie structure?

hard

A. The node for 'b' has children 'a' and 'm' directly

B. Each word creates a separate branch from root

C. The node for 'b' has children 'a' only, and 'a' has children 't' and 'l'

D. The node for 't' is the end of word for both "bat" and "batman"

Solution

1. Step 1: Analyze common prefixes in words

   Words "bat", "ball", and "batman" share prefix 'b' -> 'a'. From 'a', 't' leads to "bat" and "batman", 'l' leads to "ball".

2. Step 2: Understand Trie branching

   Node 'b' has child 'a'. Node 'a' branches to 't' and 'l'. 'm' is child of 'a'->'t'->'m' for "batman". So 'm' is not direct child of 'b'.

3. Final Answer:

   The node for 'b' has children 'a' only, and 'a' has children 't' and 'l' -> Option C

4. Quick Check:

   Trie branches at shared prefixes [OK]

Hint: Words share nodes for common prefixes only [OK]

Common Mistakes:

• Assuming all words start new branches at root
• Thinking 'm' is direct child of 'b'
• Confusing end of word nodes