Trie Node Design and Initialization in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie node and what does it typically store?

A Trie node is a building block of a Trie data structure. It typically stores a collection of child nodes (usually in an object or array) representing possible next characters, and a boolean flag to mark if the node completes a valid word.

beginner

How do you initialize a Trie node in JavaScript?

You create an object with a children property (an empty object or Map) and an isEndOfWord boolean set to false. For example: <br><code>class TrieNode {<br>  constructor() {<br>    this.children = {};<br>    this.isEndOfWord = false;<br>  }<br>}</code>

intermediate

Why do we use an object or Map for children in a Trie node?

Because each child represents a possible next character, using an object or Map allows quick lookup of child nodes by character keys, making insertion and search efficient.

beginner

What does the isEndOfWord flag represent in a Trie node?

It marks whether the path from the root to this node forms a complete valid word stored in the Trie.

beginner

Show a simple JavaScript class for a Trie node with initialization.

<code>class TrieNode {<br>  constructor() {<br>    this.children = {};<br>    this.isEndOfWord = false;<br>  }<br>}</code>

What data structure is commonly used to store children in a Trie node?

A Object or Map

B Array of numbers

C Linked list

D Stack

Children are stored in an object or Map for quick character-based lookup.

What does the isEndOfWord boolean in a Trie node indicate?

A If the node has children

B If the node marks the end of a valid word

C If the node is the root

D If the node is empty

isEndOfWord marks if the path to this node forms a complete word.

How do you initialize the children property in a Trie node in JavaScript?

A As an empty string

B As a number zero

C As an empty object {}

D As null

Children are initialized as an empty object to hold child nodes.

Which of these is NOT a typical part of a Trie node?

A Parent pointer

B Children collection

C isEndOfWord flag

D Character value

Parent pointer is not usually stored in Trie nodes; children and end-of-word flag are standard.

What is the main purpose of a Trie node?

A To hold a stack of words

B To store numbers in sorted order

C To act as a queue

D To store a single character and link to next characters

Trie nodes store characters and link to possible next characters for word storage.

Explain how a Trie node is designed and initialized in JavaScript.

Think about what each node needs to store to represent words.

Describe the role of the isEndOfWord flag and children collection in a Trie node.

Consider how the Trie knows when a word finishes.

Practice

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

easy

A. To store the entire word in one node

B. To store integer values for sorting

C. To hold only the last character of a word

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

Solution

1. Step 1: Understand Trie node role

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

2. Step 2: Compare options

   Only To store characters and links to child nodes representing prefixes correctly describes storing characters and child links for prefixes.

3. Final Answer:

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

4. Quick Check:

   Trie node = character + child links [OK]

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

Common Mistakes:

• Thinking nodes store whole words
• Confusing Trie nodes with array elements
• Assuming nodes only store last characters

2. Which of the following is the correct way to initialize a Trie node in JavaScript with an empty children object and a boolean flag isEndOfWord set to false?

easy

A. const node = { children: null, isEndOfWord: true };

B. const node = { children: [], isEndOfWord: false };

C. const node = { children: {}, isEndOfWord: false };

D. const node = { children: {}, isEndOfWord: true };

Solution

1. Step 1: Identify correct children type

   Children should be an object to map characters to nodes, so {} is correct.

2. Step 2: Check isEndOfWord initial value

   Initially, isEndOfWord should be false because the node does not end a word yet.

3. Final Answer:

   const node = { children: {}, isEndOfWord: false }; -> Option C

4. Quick Check:

   Empty object + false flag = correct initialization [OK]

Hint: Children is an object, isEndOfWord starts false [OK]

Common Mistakes:

• Using array instead of object for children
• Setting isEndOfWord true at initialization
• Setting children to null

3. Consider this JavaScript code snippet for a Trie node:

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

const node = new TrieNode();
console.log(node.isEndOfWord);
console.log(Object.keys(node.children).length);

What will be the output?

medium

A. false
0

B. true
0

C. false
undefined

D. undefined
0

Solution

1. Step 1: Check isEndOfWord value after construction

   Constructor sets isEndOfWord to false, so console.log prints false.

2. Step 2: Check children keys count

   Children is an empty object, so Object.keys(node.children).length is 0.

3. Final Answer:

   false 0 -> Option A

4. Quick Check:

   isEndOfWord = false, children keys = 0 [OK]

Hint: Empty children means zero keys; isEndOfWord defaults false [OK]

Common Mistakes:

• Assuming isEndOfWord is true by default
• Expecting children keys length to be undefined
• Confusing object keys count with children length

4. The following code attempts to create a Trie node but has an error:

function TrieNode() {
  this.children = [];
  this.isEndOfWord = false;
}

What is the main problem with this code?

medium

A. children should be an object, not an array

B. isEndOfWord should be true initially

C. Function should return a value

D. Missing semicolon after isEndOfWord assignment

Solution

1. Step 1: Analyze children data type

   Children must be an object to map characters to nodes, not an array.

2. Step 2: Check other parts

   isEndOfWord false is correct; function constructors do not need explicit return; semicolons are optional in JS.

3. Final Answer:

   children should be an object, not an array -> Option A

4. Quick Check:

   Children = object, not array [OK]

Hint: Children must be object for character keys, not array [OK]

Common Mistakes:

• Thinking arrays can map characters
• Expecting function constructors to return explicitly
• Focusing on semicolon errors

5. You want to design a Trie node class in JavaScript that supports Unicode characters as keys in children and initializes isEndOfWord to false. Which of the following implementations correctly achieves this and allows adding child nodes dynamically?

hard

A. class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = true;
}
addChild(char) {
this.children[char] = new TrieNode();
}
}

B. class TrieNode {
constructor() {
this.children = new Map();
this.isEndOfWord = false;
}
addChild(char) {
if (!this.children.has(char)) {
this.children.set(char, new TrieNode());
}
}
}

C. class TrieNode {
constructor() {
this.children = [];
this.isEndOfWord = false;
}
addChild(char) {
this.children.push(char);
}
}

D. class TrieNode {
constructor() {
this.children = new Set();
this.isEndOfWord = false;
}
addChild(char) {
this.children.add(char);
}
}

Solution

1. Step 1: Check children data structure for Unicode support

   Using Map allows any string keys including Unicode, better than plain objects.

2. Step 2: Verify isEndOfWord initialization and addChild method

   isEndOfWord is false initially, and addChild adds new TrieNode only if missing, correctly updating children Map.

3. Step 3: Compare other options

   class TrieNode { constructor() { this.children = {}; this.isEndOfWord = true; } addChild(char) { this.children[char] = new TrieNode(); } } sets isEndOfWord true initially (wrong). class TrieNode { constructor() { this.children = []; this.isEndOfWord = false; } addChild(char) { this.children.push(char); } } uses array which can't map chars to nodes. class TrieNode { constructor() { this.children = new Set(); this.isEndOfWord = false; } addChild(char) { this.children.add(char); } } uses Set which stores chars but not nodes.

4. Final Answer:

   Implementation using Map with isEndOfWord false and addChild method -> Option B

5. Quick Check:

   Map + false flag + dynamic addChild = correct Trie node [OK]

Hint: Use Map for Unicode keys and false isEndOfWord [OK]

Common Mistakes:

• Using array or Set instead of Map or object
• Setting isEndOfWord true at start
• Not checking if child exists before adding