Trie Insert Operation in DSA Typescript - Execution Trace

Concept Flow - Trie Insert Operation

Start at root node

↓

For each character in word

↓

Check if child node exists

↓

Move to child

↓

Repeat for next character

↓

Mark last node as end of word

↓

Done

Insert each character by traversing or creating nodes, then mark the last node as end of word.

Execution Sample

DSA Typescript

insert(word: string) {
  let node = this.root;
  for (const char of word) {
    if (!node.children.has(char)) {
      node.children.set(char, new TrieNode());
    }
    node = node.children.get(char)!;
  }
  node.isEnd = true;
}

Inserts a word into the trie by creating nodes for missing characters and marking the end.

Execution Table

Step	Operation	Character	Node Visited	Pointer Changes	Trie Visual State
1	Start insertion	-	root	node = root	root (children: {})
2	Check 'c' in root children	c	root	Create node for 'c'	root (children: {c}) c (children: {})
3	Move to node 'c'	c	node 'c'	node = node 'c'	root (children: {c}) c (children: {})
4	Check 'a' in node 'c' children	a	node 'c'	Create node for 'a'	root (children: {c}) c (children: {a}) a (children: {})
5	Move to node 'a'	a	node 'a'	node = node 'a'	root (children: {c}) c (children: {a}) a (children: {})
6	Check 't' in node 'a' children	t	node 'a'	Create node for 't'	root (children: {c}) c (children: {a}) a (children: {t}) t (children: {})
7	Move to node 't'	t	node 't'	node = node 't'	root (children: {c}) c (children: {a}) a (children: {t}) t (children: {})
8	Mark node 't' as end of word	-	node 't'	node.isEnd = true	root (children: {c}) c (children: {a}) a (children: {t}) t* (end)
9	Insertion complete	-	node 't'	-	root (children: {c}) c (children: {a}) a (children: {t}) t* (end)

💡 All characters processed and last node marked as end of word.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 8	Final
node	root	node 'c'	node 'a'	node 't'	node 't' (isEnd=true)	node 't' (isEnd=true)

Key Moments - 3 Insights

Why do we create a new node only if the character is not already a child?

Because if the child node exists (see step 3 and 5), we just move to it to reuse existing paths, avoiding duplicates.

Why do we mark the last node as end of word?

Marking the last node (step 8) tells the trie that a complete word ends here, distinguishing prefixes from full words.

What happens if we insert a word that shares prefix with existing words?

We reuse existing nodes for shared characters (steps 2-7), only creating new nodes for characters not present.

Visual Quiz - 3 Questions

Look at the execution table, what is the node visited at step 5?

A node 'c'

B node 'a'

C node 't'

D root

💡 Hint

Check the 'Node Visited' column at step 5 in the execution table.

At which step is the node for character 't' created?

A Step 6

B Step 3

C Step 4

D Step 2

💡 Hint

Look at the 'Pointer Changes' column for creation of nodes in the execution table.

If the word 'cat' was already in the trie, what would happen at step 2?

A Create new node for 'c'

B Mark node 'c' as end of word

C Move to existing node 'c'

D Stop insertion

💡 Hint

Refer to the condition check and pointer changes in the execution table steps.

Concept Snapshot

Trie Insert Operation:
- Start at root node
- For each character:
  - If child exists, move to it
  - Else create new child node
- Mark last node as end of word
- Reuses prefixes to save space

Full Transcript

The Trie Insert Operation starts at the root node. For each character in the word, it checks if a child node exists. If yes, it moves to that node; if not, it creates a new node. After processing all characters, it marks the last node as the end of the word. This process efficiently stores words by sharing common prefixes.