Trie Insert Operation in DSA Javascript - Execution Trace

Concept Flow - Trie Insert Operation

Start at root node

↓

For each character in word

↓

Check if child node exists

↓

Move to child

↓

Mark end of word at last char

↓

Done

Insert each character by moving through existing nodes or creating new ones, then mark the last node as end of word.

Execution Sample

DSA Javascript

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

// Insert 'cat' into trie

This code defines the TrieNode class used in the insert operation for the word 'cat', as simulated in the execution table.

Execution Table

Step	Operation	Current Character	Node Created	Pointer Changes	Trie Visual State
1	Start at root	-	No	current = root	root {children: {}, isEndOfWord: false}
2	Check 'c' child	c	Yes	root.children['c'] = new TrieNode()	root {c} → node_c {children: {}, isEndOfWord: false}
3	Move to 'c' node	c	No	current = node_c	root {c} → node_c
4	Check 'a' child	a	Yes	node_c.children['a'] = new TrieNode()	root {c} → node_c {a} → node_a
5	Move to 'a' node	a	No	current = node_a	root {c} → node_c {a} → node_a
6	Check 't' child	t	Yes	node_a.children['t'] = new TrieNode()	root {c} → node_c {a} → node_a {t} → node_t
7	Move to 't' node	t	No	current = node_t	root {c} → node_c {a} → node_a {t} → node_t
8	Mark end of word	-	No	node_t.isEndOfWord = true	root {c} → node_c {a} → node_a {t} → node_t*
9	Done	-	No	-	Trie contains 'cat'

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

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
current	root	node_c	node_a	node_t	node_t	node_t
node_c.children	{}	{}	{a: node_a}	{a: node_a}	{a: node_a}	{a: node_a}
node_a.children	{}	{}	{}	{t: node_t}	{t: node_t}	{t: node_t}
node_t.isEndOfWord	false	false	false	false	true	true

Key Moments - 3 Insights

Why do we create a new node only if the child does not exist?

Because if the child node for a character already exists (see steps 3, 5, 7), we just move to it to avoid overwriting existing words.

Why do we mark isEndOfWord only after processing the last character?

Marking isEndOfWord at 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 and only create new nodes for new characters, preserving the trie structure efficiently.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'current' after step 4?

A node_a

B node_c

C root

D node_t

💡 Hint

Check the 'variable_tracker' row for 'current' after step 4

At which step is the isEndOfWord flag set to true?

A Step 6

B Step 8

C Step 4

D Step 2

💡 Hint

Look at the 'execution_table' row with 'Mark end of word' operation

If the word 'car' was inserted after 'cat', which step would create a new node?

A For character 'c'

B For character 'a'

C For character 'r'

D No new nodes needed

💡 Hint

Shared prefix nodes exist for 'c' and 'a', new node needed only for differing character

Concept Snapshot

Trie Insert Operation:
- Start at root node
- For each character:
  - If child exists, move to it
  - Else create new child node
- After last char, mark node as end of word
- Efficiently stores words sharing prefixes

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 no, it creates a new node. After processing all characters, it marks the last node as the end of a word. This process allows efficient storage of words with shared prefixes by reusing existing nodes and only adding new nodes when necessary.