Trie Node Design and Initialization in DSA Typescript - Time & Space Complexity

Time Complexity: Trie Node Design and Initialization

O(1)

Understanding Time Complexity

We want to understand how much work it takes to create a single node in a Trie.

This helps us see how the Trie grows as we add words.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class TrieNode {
  children: Map;
  isEndOfWord: boolean;

  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}
    

This code creates a Trie node with a map for children and a flag for word end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Creating an empty map and setting a boolean flag.
• How many times: Once per node creation.

How Execution Grows With Input

Each time we create a node, we do a fixed amount of work.

Input Size (n nodes)	Approx. Operations
10	10 simple initializations
100	100 simple initializations
1000	1000 simple initializations

Pattern observation: The work grows directly with the number of nodes created.

Final Time Complexity

Time Complexity: O(1)

This means creating each Trie node takes the same small amount of time, no matter what.

Common Mistake

[X] Wrong: "Creating a Trie node takes longer as the Trie grows because it has more children."

[OK] Correct: Each node starts empty with no children; the initialization work is always the same small step.

Interview Connect

Understanding this simple step helps you build efficient Tries and shows you know how data structures grow step-by-step.

Self-Check

"What if we used an array of fixed size 26 instead of a Map for children? How would the time complexity change?"

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