Why Trie Node Design and Initialization in DSA Typescript?

The Big Idea

Discover how a simple node design can power instant word searches like magic!

The Scenario

Imagine you want to quickly find words in a huge dictionary by typing their prefixes, like searching for all words starting with 'app'. Doing this by checking each word one by one is like flipping through every page of a giant book to find matches.

The Problem

Manually searching each word is very slow and tiring. It wastes time and can easily lead to mistakes, especially when the list is very long. You might miss words or take too long to find what you want.

The Solution

A Trie is like a smart tree that organizes words by their letters. Each node represents a letter, and paths from the root form words. This design lets you find all words with a prefix quickly by just following the path of letters, without checking every word.

Before vs After

✗ Before

const words = ['apple', 'app', 'bat'];
const prefix = 'app';
const results = [];
for (const word of words) {
  if (word.startsWith(prefix)) {
    results.push(word);
  }
}

✓ After

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

// Insert and search methods use this node design for fast prefix search

What It Enables

It enables lightning-fast prefix searches and efficient word storage, making autocomplete and spell-check features possible.

Real Life Example

When you type in a search box on your phone, the suggestions appear instantly because a Trie quickly finds all words starting with what you typed.

Key Takeaways

Manual word search is slow and error-prone.

Trie nodes represent letters and link to next letters.

Trie design makes prefix search fast and efficient.

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