Trie Insert Operation in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting words into a Trie

What is the printed structure of the Trie after inserting the words "cat", "car", and "dog" in this order?

DSA Typescript

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

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

  insert(word: string) {
    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)!;
    }
    node.isEndOfWord = true;
  }

  print(node: TrieNode = this.root, prefix: string = '') {
    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.insert("dog");
trie.print();

A

"cat"
"car"
"dog"

B

"cat"
"dog"
"car"

C

"dog"
"car"
"cat"

D

"car"
"cat"
"dog"

💡 Hint

Think about how the children Map stores keys and how iteration order affects output.

The Map stores keys in insertion order. For the first two words, 'cat' and 'car', the common prefix 'ca' shares nodes. The children of 'ca' are 't' and 'r'. Since 'r' was inserted before 't' (from 'car' before 'cat'), 'car' prints before 'cat'. Then 'dog' is separate and prints last.

🧠 Conceptual

intermediate

Number of nodes after inserting words in a Trie

After inserting the words "bat", "bath", and "baton" into an empty Trie, how many nodes does the Trie contain?

A 9

B 7

C 8

D 10

💡 Hint

Count shared prefixes carefully to avoid double counting nodes.

The words share the prefix 'bat' (3 nodes). 'bath' adds 'h' (1 node), 'baton' adds 'o' and 'n' (2 nodes). Total nodes = 3 + 1 + 2 + 1 (root node counted once) = 7 nodes.

🔧 Debug

advanced

Identify the error in Trie insert method

What error will this Trie insert method cause when inserting the word "apple"?

DSA Typescript

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

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

  insert(word: string) {
    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)!;
    }
    node.isEndOfWord = true;
  }
}

A Runtime error: Cannot read property 'get' of undefined

B Infinite loop during insertion

C Incorrect insertion: overwrites existing nodes causing loss of data

D No error, inserts correctly

💡 Hint

Check the condition that decides when to create a new node.

The condition is reversed. It creates a new node when the child already exists, overwriting it and losing previous data. This causes incorrect Trie structure.

📝 Syntax

advanced

Syntax error in Trie insert method

Which option contains a syntax error in the insert method of a Trie?

DSA Typescript

insert(word: string) {
  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)!;
  }
  node.isEndOfWord = true;
}

A Missing semicolon after set method call causes syntax error

B Missing braces for if statement but valid in TypeScript

C Incorrect use of exclamation mark causes syntax error

D Missing parentheses in for loop causes syntax error

💡 Hint

Check punctuation after method calls.

In TypeScript, missing semicolon after a statement can cause syntax errors depending on context. Here, missing semicolon after set call can cause issues.

🚀 Application

expert

Final Trie structure after multiple insertions

After inserting the words "to", "tea", "ted", "ten", and "inn" into an empty Trie, which of the following represents the correct set of words printed by a preorder traversal that prints words when isEndOfWord is true?

DSA Typescript

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

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

  insert(word: string) {
    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)!;
    }
    node.isEndOfWord = true;
  }

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

const trie = new Trie();
trie.insert("to");
trie.insert("tea");
trie.insert("ted");
trie.insert("ten");
trie.insert("inn");
trie.print();

A

"to"
"tea"
"ted"
"ten"
"inn"

B

"tea"
"ted"
"ten"
"to"
"inn"

C

"to"
"inn"
"tea"
"ted"
"ten"

D

"inn"
"tea"
"ted"
"ten"
"to"

💡 Hint

Remember that Map iteration preserves insertion order of children.

Words are inserted in order: to, tea, ted, ten, inn. The print method does preorder traversal printing words when isEndOfWord is true. The order reflects insertion order of children nodes.

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