Trie Insert Operation in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after inserting words into a Trie?

Consider a Trie data structure where each node stores children in an object and a boolean flag for end of word. After inserting the words "cat" and "car", what is the printed structure of the root node's children keys?

DSA Javascript

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }
}

const trie = new Trie();
trie.insert("cat");
trie.insert("car");
console.log(Object.keys(trie.root.children));

A ["c", "a", "t", "r"]

B ["c", "a"]

C ["c"]

D ["a"]

💡 Hint

Think about the first letter of each inserted word and how the root node stores children.

The root node only stores the first letters of inserted words as keys in its children object. Both "cat" and "car" start with 'c', so the root's children keys contain only ['c'].

❓ Predict Output

intermediate

What is the value of isEndOfWord after inserting 'dog' and 'dot'?

After inserting the words "dog" and "dot" into an empty Trie, what is the value of isEndOfWord for the node representing the letter 'g' in "dog"?

DSA Javascript

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }
}

const trie = new Trie();
trie.insert("dog");
trie.insert("dot");
console.log(trie.root.children['d'].children['o'].children['g'].isEndOfWord);

A undefined

B true

C false

D TypeError

💡 Hint

Check if the last character node of the inserted word marks the end of a word.

The node for 'g' in "dog" is the last character node of the word "dog", so its isEndOfWord is set to true during insertion.

❓ Predict Output

advanced

What is the output after inserting overlapping words in a Trie?

Given the following insertions into a Trie: "bat", "bath", and "baton", what is the value of isEndOfWord for the node representing 't' in "bat"?

DSA Javascript

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }
}

const trie = new Trie();
trie.insert("bat");
trie.insert("bath");
trie.insert("baton");
console.log(trie.root.children['b'].children['a'].children['t'].isEndOfWord);

A true

B false

C undefined

D ReferenceError

💡 Hint

Remember that each inserted word marks the end of its last character node.

The node for 't' in "bat" is the end of the word "bat", so its isEndOfWord is true even though longer words share the prefix.

🧠 Conceptual

advanced

How many nodes are created after inserting 'apple' and 'app' into an empty Trie?

If you insert the words "apple" and "app" into an empty Trie, how many total nodes (including the root) will the Trie have?

A 7

B 5

C 8

D 6

💡 Hint

Count nodes for unique characters only; shared prefixes reuse nodes.

The root node plus nodes for 'a', 'p', 'p', 'l', 'e' total 6 nodes. Since "app" shares the first three letters, no new nodes are added for it. So total nodes = 1 (root) + 5 = 6 nodes. But careful: root + a + p + p + l + e = 6 nodes total. So answer is 6.

❓ Predict Output

expert

What is the output after inserting words and checking a non-existent path?

After inserting "hello" and "helium" into a Trie, what is the output of accessing trie.root.children['h'].children['e'].children['l'].children['x']?

DSA Javascript

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }
}

const trie = new Trie();
trie.insert("hello");
trie.insert("helium");
console.log(trie.root.children['h'].children['e'].children['l'].children['x']);

A undefined

B null

C {}

D TypeError

💡 Hint

Check if the path for 'x' exists under the given nodes.

The path for 'x' does not exist under the node for 'l', so accessing children['x'] returns undefined.

Practice

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

easy

A. To count the total words stored in the Trie

B. To delete a word from the Trie

C. To search for a word in the Trie

D. To add a new word character by character into 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 nodes if they don't exist.

2. Step 2: Compare with other operations

   Deleting removes words, searching finds words, and counting totals words, but insert specifically adds words.

3. Final Answer:

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

4. Quick Check:

   Insert = Add word step-by-step [OK]

Hint: Insert means adding word letters stepwise [OK]

Common Mistakes:

• Confusing insert with search or delete
• Thinking insert adds whole word as one node
• Assuming insert counts words

2. Which of the following is the correct way to start inserting a word "cat" into an empty Trie in JavaScript?

easy

A. for (let char of word) { if (!node.children[char]) node.children[char] = new TrieNode(); node = node.children[char]; }

B. for (let i = 0; i < word.length; i++) { node = node.children[word[i]]; }

C. while (word) { node.children[word[0]] = new TrieNode(); word = word.slice(1); }

D. node.children[word] = new TrieNode();

Solution

1. Step 1: Analyze the loop for insertion

   for (let char of word) { if (!node.children[char]) node.children[char] = new TrieNode(); node = node.children[char]; } loops over each character, checks if child node exists, creates if not, then moves to that child node.

2. Step 2: Check other options for correctness

   for (let i = 0; i < word.length; i++) { node = node.children[word[i]]; } does not create nodes if missing. while (word) { node.children[word[0]] = new TrieNode(); word = word.slice(1); } modifies the word string but does not move node properly. node.children[word] = new TrieNode(); tries to add whole word as one child.

3. Final Answer:

   for (let char of word) { if (!node.children[char]) node.children[char] = new TrieNode(); node = node.children[char]; } -> Option A

4. Quick Check:

   Loop chars, create missing nodes, move node [OK]

Hint: Loop chars, create missing nodes, move node [OK]

Common Mistakes:

• Not creating nodes when missing
• Assigning whole word as one child
• Not updating current node pointer

3. What will be the structure of the Trie after inserting the words ["bat", "ball"] in order? Consider each node stores children in an object and a boolean isEnd for word end.

medium

A. {"b":{"a":{"t":{"isEnd":false},"l":{"l":{"isEnd":true}}}}}

B. {"b":{"a":{"t":{"isEnd":true},"l":{"isEnd":true}}}}

C. {"b":{"a":{"t":{"isEnd":true},"l":{"l":{"isEnd":true}}}}}

D. {"b":{"a":{"t":{"isEnd":true}},"l":{"l":{"isEnd":true}}}}

Solution

1. Step 1: Insert "bat" into empty Trie

   Creates nodes b -> a -> t with t's isEnd true.

2. Step 2: Insert "ball" next

   Nodes b -> a exist, then add l -> l with last l's isEnd true.

3. Final Answer:

   {"b":{"a":{"t":{"isEnd":true},"l":{"l":{"isEnd":true}}}}} -> Option C

4. Quick Check:

   Both words share prefix 'ba', separate branches for 't' and 'll' [OK]

Hint: Shared prefix nodes, separate branches for different suffixes [OK]

Common Mistakes:

• Marking wrong nodes as word end
• Not creating second 'l' node for 'ball'
• Overwriting nodes incorrectly

4. Given this insert function snippet, what is the bug?

insert(word) {
  let node = this.root;
  for (let char of word) {
    if (!node.children[char]) {
      node.children[char] = new TrieNode();
    }
    node = node.children;
  }
  node.isEnd = true;
}

medium

A. Missing check for empty word input

B. node is assigned to node.children instead of node.children[char]

C. isEnd should be set before the loop

D. Children should be an array, not an object

Solution

1. Step 1: Check node update inside loop

   Inside loop, node is set to node.children (object), not node.children[char] (child node), so traversal breaks.

2. Step 2: Confirm correct pointer update

   Correct is node = node.children[char] to move down the Trie properly.

3. Final Answer:

   node is assigned to node.children instead of node.children[char] -> Option B

4. Quick Check:

   Update node to child node, not children object [OK]

Hint: Update node to child node, not children object [OK]

Common Mistakes:

• Assigning node to children object instead of child node
• Setting isEnd too early
• Ignoring empty input check

5. You want to insert the words ["apple", "app", "ape"] into a Trie and then check if the word "app" is a complete word in the Trie. Which approach correctly handles this scenario?

hard

A. Insert each word character by character, mark isEnd true at last character; then search for "app" checking isEnd at last node

B. Insert all words, but mark isEnd true only for the longest word; search ignores isEnd

C. Insert words as full strings in one node; search by matching full string keys

D. Insert words without marking isEnd; search by checking if path exists

Solution

1. Step 1: Insert words with isEnd marking

   Each word is inserted letter by letter; isEnd is set true at last letter node to mark complete words.

2. Step 2: Search for "app" with isEnd check

   Search traverses nodes for 'a'->'p'->'p' and checks isEnd true to confirm "app" is a complete word, not just prefix.

3. Final Answer:

   Insert each word character by character, mark isEnd true at last character; then search for "app" checking isEnd at last node -> Option A

4. Quick Check:

   Mark word ends, check isEnd to confirm full word [OK]

Hint: Mark word ends with isEnd, check isEnd when searching [OK]

Common Mistakes:

• Not marking isEnd for shorter words
• Treating prefixes as complete words without isEnd
• Storing whole words as single nodes