Trie Node Design and Initialization in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a TrieNode class with a children map.

DSA Typescript

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

  constructor() {
    this.children = new [1]();
  }
}

Drag options to blanks, or click blank then click option'

ASet

BMap

CArray

DObject

Attempts:

3 left

💡 Hint

Common Mistakes

Using Array instead of Map for children.

Using Set which does not store key-value pairs.

A TrieNode uses a Map to store children nodes keyed by characters for efficient lookup.

2fill in blank

medium

Complete the code to add a child node for a given character in the TrieNode.

DSA Typescript

addChild(char: string) {
  if (!this.children.has(char)) {
    this.children.set(char, new [1]());
  }
}

Drag options to blanks, or click blank then click option'

AMap

BNode

CTrieNode

DSet

Attempts:

3 left

💡 Hint

Common Mistakes

Using Map or Set instead of TrieNode for child nodes.

Using an undefined class name like Node.

Each child is a new TrieNode instance representing the next character.

3fill in blank

hard

Fix the error in the constructor to initialize isEndOfWord correctly.

DSA Typescript

constructor() {
  this.children = new Map();
  this.isEndOfWord = [1];
}

Drag options to blanks, or click blank then click option'

Afalse

Btrue

Cnull

Dundefined

Attempts:

3 left

💡 Hint

Common Mistakes

Setting isEndOfWord to true by default.

Using null or undefined which are not booleans.

isEndOfWord should start as false because the node initially does not mark the end of a word.

4fill in blank

hard

Fill both blanks to check if a character exists and retrieve its child node.

DSA Typescript

getChild(char: string): TrieNode | undefined {
  if (this.children.[1](char)) {
    return this.children.[2](char);
  }
  return undefined;
}

Drag options to blanks, or click blank then click option'

Ahas

Bget

Cset

Ddelete

Attempts:

3 left

💡 Hint

Common Mistakes

Using set() instead of get() to retrieve a value.

Using delete() which removes a key.

Use has() to check existence and get() to retrieve the child node from the Map.

5fill in blank

hard

Fill all three blanks to implement a method that marks the node as end of a word and adds a child if missing.

DSA Typescript

markEndAndAddChild(char: string) {
  this.isEndOfWord = [1];
  if (!this.children.[2](char)) {
    this.children.[3](char, new TrieNode());
  }
}

Drag options to blanks, or click blank then click option'

Atrue

Bhas

Cset

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Setting isEndOfWord to false instead of true.

Using get() instead of has() to check existence.

Using delete() instead of set() to add child.

Set isEndOfWord to true, check existence with has(), and add child with set().

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