Trie Node Design and Initialization in DSA Typescript

Mental Model

A trie node holds links to next letters and a marker if a word ends here, like a branching path for words.

Analogy: Imagine a tree where each branch is a letter, and leaves mark the end of a word, so you can follow branches to spell words.

root
 ↓
[ ] -> [ ] -> [ ] -> ... (each box is a child node for a letter)
  ↑
  isEnd=false

Dry Run Walkthrough

Input: Create a trie node for the root with empty children and isEnd false

Goal: Initialize a trie node that can hold up to 26 children and mark if a word ends here

Step 1: Create an array of 26 nulls for children nodes

children: [null, null, null, ..., null] (26 times), isEnd: false

Why: We need space to store links to next letters, one slot per letter

Step 2: Set isEnd flag to false

children: [null, null, null, ..., null], isEnd: false

Why: Initially, no word ends at this node

Result:

children: [null, null, null, ..., null], isEnd: false

Annotated Code

DSA Typescript

class TrieNode {
  children: Array<TrieNode | null>;
  isEnd: boolean;

  constructor() {
    this.children = new Array(26).fill(null); // create 26 slots for letters a-z
    this.isEnd = false; // no word ends here initially
  }
}

// Driver code to create a root node
const root = new TrieNode();
console.log(root.children);
console.log(root.isEnd);

this.children = new Array(26).fill(null);

initialize children array with 26 nulls for each letter slot

this.isEnd = false;

mark node as not ending any word initially

Output

[null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null]

false

Complexity Analysis

Time: O(1) because initialization creates a fixed size array of 26 elements

Space: O(1) for each node since children array size is fixed at 26

vs Alternative: Compared to dynamic structures like maps, fixed array uses constant space and faster access but more memory upfront

Edge Cases

Creating a node with no children

Children array is filled with nulls, no links exist yet

DSA Typescript

this.children = new Array(26).fill(null);

Marking a node as end of word

isEnd flag is set to true when a word finishes at this node

DSA Typescript

this.isEnd = true;

When to Use This Pattern

When you need to store many words sharing prefixes efficiently, use a trie node design with fixed children array and end marker.

Common Mistakes

Mistake: Using a dynamic array or list for children causing slower access
Fix: Use a fixed size array of length 26 for constant time access by letter index

Mistake: Not initializing isEnd flag leading to wrong word end detection
Fix: Always initialize isEnd to false in constructor

Summary

A trie node holds 26 children pointers and a boolean to mark word end.

Use it when building prefix trees to store many words efficiently.

The key is fixed size children array for fast letter lookup and isEnd flag for word completion.

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