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

Recall & Review

beginner

What is a Trie Node in a Trie data structure?

A Trie Node is a building block of a Trie. It stores links to child nodes for each character and a flag to mark if it ends a word.

beginner

How do you initialize the children of a Trie Node in TypeScript?

You initialize children as an object or map where keys are characters and values are Trie Nodes, starting empty.

beginner

What property in a Trie Node indicates the end of a word?

A boolean property, often named 'isEndOfWord', marks if the node completes a valid word.

beginner

Show a simple TypeScript class snippet for a Trie Node with children and end flag.

class TrieNode {
  children: { [key: string]: TrieNode } = {};
  isEndOfWord: boolean = false;
}

intermediate

Why do we use an object or map for children in a Trie Node instead of an array?

Because children represent characters which are keys, using an object/map allows quick lookup by character without wasting space.

What does the 'isEndOfWord' property in a Trie Node represent?

A Marks the node as the end of a valid word

B Counts the number of children nodes

C Stores the character of the node

D Indicates if the node has any children

The 'isEndOfWord' boolean marks if the node completes a valid word in the Trie.

How are children nodes typically stored in a Trie Node in TypeScript?

A As an object with characters as keys and Trie Nodes as values

B As a simple string

C As a number array

D As a boolean flag

Children are stored as an object mapping characters to Trie Nodes for quick access.

Which of these is NOT a typical property of a Trie Node?

A children

B isEndOfWord

C parentNode

D character

While some implementations may track parent nodes, it is not a typical required property.

What is the initial value of 'isEndOfWord' when a Trie Node is created?

A true

B false

C null

D undefined

'isEndOfWord' starts as false because the node does not represent the end of a word initially.

Why is an object preferred over an array for children in a Trie Node?

A Arrays cannot store nodes

B Arrays are slower to access

C Objects use less memory always

D Because characters are keys, not indexes

Characters are keys, so an object allows direct access by character instead of numeric index.

Describe how you would design and initialize a Trie Node in TypeScript.

Think about what data each node needs to store for the Trie to work.

Explain why the children property in a Trie Node is an object instead of an array.

Consider how you find the next node for a given character.

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