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?"