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.