Trie Node Design and Initialization in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Node Initialization

What is the output of the following TypeScript code that initializes a Trie node and prints its children keys?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode>;
  isEndOfWord: boolean;

  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}

const node = new TrieNode();
console.log(Array.from(node.children.keys()));

A [null]

B [undefined]

C []

D [" "]

💡 Hint

Think about what keys exist in a newly created empty Map.

A new TrieNode has an empty Map for children, so no keys exist. Converting keys to an array results in an empty array [].

❓ Predict Output

intermediate

Trie Node Children After Insert

After inserting a child node with key 'a' into a TrieNode's children Map, what is the output of printing the keys?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode>;
  isEndOfWord: boolean;

  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}

const node = new TrieNode();
node.children.set('a', new TrieNode());
console.log(Array.from(node.children.keys()));

A [undefined]

B ['a']

C ['A']

D []

💡 Hint

Check what key was added to the Map.

The key 'a' was added to the children Map, so printing keys shows ['a'].

🔧 Debug

advanced

Identify the Error in TrieNode Constructor

What error will this TypeScript code produce when creating a TrieNode instance?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode>;
  isEndOfWord: boolean;

  constructor() {
    this.children = {};
    this.children.set('a', new TrieNode());
    this.isEndOfWord = false;
  }
}

const node = new TrieNode();

A TypeError: this.children.set is not a function

B SyntaxError: Unexpected token {

C No error, code runs fine

D ReferenceError: TrieNode is not defined

💡 Hint

Check the type assigned to children and how Map methods are used.

Assigning {} to children means it's a plain object, not a Map. Calling Map methods like set on it causes TypeError.

🧠 Conceptual

advanced

Purpose of isEndOfWord in TrieNode

What is the main purpose of the isEndOfWord boolean property in a TrieNode?

A To mark if the node represents the end of a valid word

B To store the number of children nodes

C To keep track of the depth of the node in the Trie

D To hold the character value of the node

💡 Hint

Think about how a Trie distinguishes complete words from prefixes.

isEndOfWord marks nodes that complete a valid word, differentiating them from nodes that are just prefixes.

❓ Predict Output

expert

Final Trie Structure After Multiple Insertions

Given the following code inserting words into a Trie, what is the output of printing the root node's children keys?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode>;
  isEndOfWord: boolean;

  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}

class Trie {
  root: TrieNode;

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

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

const trie = new Trie();
trie.insert('cat');
trie.insert('car');
trie.insert('dog');
console.log(Array.from(trie.root.children.keys()));

A ['cat', 'car', 'dog']

B ['a', 'o']

C []

D ['c', 'd']

💡 Hint

The root's children keys are the first letters of inserted words.

Words 'cat' and 'car' start with 'c', 'dog' starts with 'd', so root children keys are ['c', 'd'].

Practice

1. What is the primary purpose of a Trie node in a Trie data structure?

easy

A. To store characters and links to child nodes representing prefixes

B. To store integer values for sorting

C. To hold a single string value only

D. To act as a queue for BFS traversal

Solution

1. Step 1: Understand Trie node role

   A Trie node stores a character and links to child nodes representing possible next characters in words.

2. Step 2: Eliminate incorrect options

   The remaining options do not describe the Trie node's role correctly.

3. Final Answer:

   To store characters and links to child nodes representing prefixes -> Option A

4. Quick Check:

   Trie node = character + child links [OK]

Hint: Trie nodes hold characters and children, not full words [OK]

Common Mistakes:

• Thinking Trie nodes store full words
• Confusing Trie nodes with arrays or queues
• Assuming Trie nodes store integer values

2. Which of the following is the correct TypeScript syntax to declare a Trie node class with a children map and an endOfWord boolean?

easy

A. class TrieNode { children: Map; endOfWord: boolean; constructor() { this.children = new Map(); this.endOfWord = true; } }

B. class TrieNode { children: Map; endOfWord: boolean; constructor() { this.children = new Map(); this.endOfWord = false; } }

C. class TrieNode { children: string[]; endOfWord: string; constructor() { this.children = []; this.endOfWord = ''; } }

D. class TrieNode { children: Map; endOfWord: boolean; constructor() { this.children = new Map(); this.endOfWord = false; } }

Solution

1. Step 1: Check children type

   Children should be a Map from string to TrieNode, not string[] or Map.

2. Step 2: Check endOfWord type and initialization

   endOfWord should be boolean, initialized to false.

3. Final Answer:

   class TrieNode { children: Map; endOfWord: boolean; constructor() { this.children = new Map(); this.endOfWord = false; } } -> Option B

4. Quick Check:

   Children: Map<string, TrieNode> + boolean endOfWord=false [OK]

Hint: Children map keys are characters (string), values are TrieNodes [OK]

Common Mistakes:

• Using array instead of Map for children
• Using wrong types for endOfWord
• Initializing endOfWord to true by default

3. Given the following TypeScript TrieNode class and code snippet, what will be the output of console.log(root.children.has('a')) after execution?

class TrieNode {
  children: Map;
  endOfWord: boolean;
  constructor() {
    this.children = new Map();
    this.endOfWord = false;
  }
}

const root = new TrieNode();
root.children.set('a', new TrieNode());

medium

A. undefined

B. false

C. true

D. Error

Solution

1. Step 1: Understand children map after insertion

   We add a key 'a' with a new TrieNode as value to root.children map.

2. Step 2: Check if 'a' key exists

   Calling root.children.has('a') returns true because 'a' was added.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Map has key 'a' = true [OK]

Hint: Map.has(key) returns true if key was set before [OK]

Common Mistakes:

• Assuming has returns the value instead of boolean
• Confusing undefined with false
• Expecting error due to missing key

4. Identify the error in the following TypeScript TrieNode class code snippet:

class TrieNode {
  children: Map;
  endOfWord: boolean;
  constructor() {
    this.children = new Map();
    this.endOfWord = 'false';
  }
}

medium

A. endOfWord is assigned a string instead of boolean

B. children map is not initialized

C. Missing semicolon after constructor

D. Map keys should be number, not string

Solution

1. Step 1: Check endOfWord type and assignment

   endOfWord is declared boolean but assigned string 'false', causing type error.

2. Step 2: Verify children initialization and syntax

   children map is correctly initialized; semicolons are optional in TypeScript; keys as string are correct.

3. Final Answer:

   endOfWord is assigned a string instead of boolean -> Option A

4. Quick Check:

   Boolean variable assigned string = error [OK]

Hint: Boolean variables must be true or false, not strings [OK]

Common Mistakes:

• Assigning 'false' (string) instead of false (boolean)
• Thinking Map keys must be numbers
• Confusing missing semicolons as errors

5. You want to design a TrieNode class in TypeScript that supports Unicode characters as keys and efficiently checks if a node marks the end of a word. Which of the following is the best design choice?

hard

A. Use a Set<string> for children and a boolean endOfWord initialized to true

B. Use an object with fixed keys for children and a string endOfWord to store word

C. Use an array of TrieNode for children indexed by character code and endOfWord as number

D. Use a Map for children and a boolean endOfWord initialized to false

Solution

1. Step 1: Consider Unicode support for children keys

   Map supports any string keys including Unicode characters efficiently.

2. Step 2: Check endOfWord type for marking word end

   Boolean endOfWord initialized to false is standard to mark if node ends a word.

3. Step 3: Evaluate other options

   Objects with fixed keys limit flexibility; arrays indexed by char code waste space; Set<string> cannot map to child nodes.

4. Final Answer:

   Use a Map for children and a boolean endOfWord initialized to false -> Option D

5. Quick Check:

   Unicode keys + boolean flag = Use a Map for children and a boolean endOfWord initialized to false [OK]

Hint: Map handles Unicode keys best [OK]

Common Mistakes:

• Using arrays limits Unicode support
• Using Set for children loses child node mapping
• Using string instead of boolean for endOfWord