Trie Insert Operation in DSA Go - 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

Start at the root, for each letter check if child exists; if not, create it. Move down nodes until word ends, then mark last node as word end.

Execution Sample

DSA Go

func Insert(word string) {
  current := root
  for _, ch := range word {
    if current.children[ch] == nil {
      current.children[ch] = newNode()
    }
    current = current.children[ch]
  }
  current.isEnd = true
}

Inserts a word into the trie by creating nodes for missing letters and marking the last node as end.

Execution Table

Step	Operation	Current Character	Node Created	Pointer Changes	Trie Visual State
1	Start insertion	-	No	current points to root	root (empty)
2	Check 'c'	c	Yes	root.children['c'] = newNode; current moves to 'c'	root └─ c
3	Check 'a'	a	Yes	'c'.children['a'] = newNode; current moves to 'a'	root └─ c └─ a
4	Check 't'	t	Yes	'a'.children['t'] = newNode; current moves to 't'	root └─ c └─ a └─ t
5	Mark end	-	No	current.isEnd = true	root └─ c └─ a └─ t* (end)
6	Insertion complete	-	No	-	root └─ c └─ a └─ t* (end)

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
current	root	node 'c'	node 'a'	node 't'	node 't' (isEnd=true)	node 't' (isEnd=true)
node created	none	node 'c'	node 'a'	node 't'	none	none

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, we just move to it to avoid overwriting existing words. See execution_table rows 2-4 where nodes are created only when missing.

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

Marking the last node as end tells the trie that a complete word ends here. Without this, the trie can't distinguish between prefixes and full words. See execution_table row 5.

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

We reuse existing nodes for shared prefix characters and create new nodes only for new suffix characters. This is shown in the flow where existing children are checked before creating new nodes.

Visual Quiz - 3 Questions

Look at the execution_table, what node does 'current' point to after step 3?

A node 'c'

B node 'a'

C node 't'

D root

💡 Hint

Check variable_tracker column 'After Step 3' for 'current' value.

At which step is the last node marked as end of word?

A Step 4

B Step 3

C Step 5

D Step 6

💡 Hint

See execution_table row where 'current.isEnd = true' is set.

If the word inserted was 'car' instead of 'cat', which step would create the node for 'r'?

A Step 4

B Step 3

C Step 5

D Step 2

💡 Hint

Insertion creates nodes for each new character; 'r' is the third character, so step 4.

Concept Snapshot

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

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 not, it creates a new node. Then it moves the current pointer to that child node. After processing all characters, it marks the last node as the end of a word. This process allows the trie to store words sharing prefixes efficiently. The execution table shows each step, node creation, pointer changes, and the trie state. The variable tracker follows the current pointer and node creation. Key moments clarify why nodes are created only when missing and why marking the end is important. The visual quiz tests understanding of pointer positions and steps.

Practice

1. What is the main purpose of the Insert operation in a Trie data structure?

easy

A. To delete a word from the Trie

B. To add a new word by creating nodes for each character

C. To search for a word in the Trie

D. To count the total words stored in the Trie

Solution

1. Step 1: Understand the Insert operation

   The Insert operation adds a word by creating nodes for each character if they don't exist.

2. Step 2: Differentiate from other operations

   Deleting removes words, searching finds words, counting totals words. Insert specifically adds words.

3. Final Answer:

   To add a new word by creating nodes for each character -> Option B

4. Quick Check:

   Insert = Add word nodes [OK]

Hint: Insert means adding nodes for each character [OK]

Common Mistakes:

• Confusing insert with search or delete
• Thinking insert counts words
• Assuming insert modifies existing words

2. Which of the following is the correct way to declare a Trie node struct in Go for insertion?

easy

A. type TrieNode struct { children map[rune]*TrieNode; isEnd bool }

B. type TrieNode struct { children []int; isEnd int }

C. type TrieNode struct { children map[string]int; isEnd string }

D. type TrieNode struct { children []string; isEnd bool }

Solution

1. Step 1: Identify correct children type for TrieNode

   Children should map characters (rune) to TrieNode pointers for branching.

2. Step 2: Check isEnd type

   isEnd is a boolean indicating if node ends a word.

3. Final Answer:

   type TrieNode struct { children map[rune]*TrieNode; isEnd bool } -> Option A

4. Quick Check:

   Children map[rune]*TrieNode and isEnd bool [OK]

Hint: Children map with rune keys and bool isEnd [OK]

Common Mistakes:

• Using slice instead of map for children
• Wrong data types for children or isEnd
• Using string keys instead of rune

3. What will be the output after inserting the words "cat" and "car" into an empty Trie and then checking if the node for 'a' under 'c' has children?

medium

A. nil

B. false

C. true

D. runtime error

Solution

1. Step 1: Insert "cat" and "car" into Trie

   Both words share prefix 'c' -> 'a'. After insertion, node 'a' has children 't' and 'r'.

2. Step 2: Check if node 'a' under 'c' has children

   Since 'a' node has two children nodes ('t' and 'r'), it has children, so true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Shared prefix node has children = true [OK]

Hint: Shared prefix nodes have children after insert [OK]

Common Mistakes:

• Assuming node 'a' has no children
• Confusing node existence with children presence
• Expecting nil or error instead of true

4. Given this Go code snippet for inserting a word into a Trie, what is the bug?

func (t *TrieNode) Insert(word string) {
    node := t
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

medium

A. children map is not initialized before use

B. Loop variable ch should be int, not rune

C. isEnd should be set before loop

D. Function should return a value

Solution

1. Step 1: Check initialization of children map

   The children map must be initialized (e.g., make(map[rune]*TrieNode)) before inserting nodes.

2. Step 2: Identify impact of missing initialization

   Without initialization, accessing children[ch] causes runtime panic (nil map assignment).

3. Final Answer:

   children map is not initialized before use -> Option A

4. Quick Check:

   Uninitialized map causes runtime error [OK]

Hint: Always initialize map before inserting keys [OK]

Common Mistakes:

• Ignoring map initialization
• Misunderstanding rune vs int for keys
• Thinking isEnd needs early assignment

5. You want to insert the words ["go", "gone", "guild"] into a Trie. After insertion, how many children does the root node have, and why?

hard

A. 0, because root has no children

B. 3, because there are three words

C. 2, because 'go' and 'guild' share 'g' but 'gone' differs

D. 1, because all words start with 'g'

Solution

1. Step 1: Analyze first characters of all words

   All words start with the letter 'g', so root node will have one child for 'g'.

2. Step 2: Understand Trie root children count

   Root children count equals distinct first letters of inserted words, here only 'g'.

3. Final Answer:

   1, because all words start with 'g' -> Option D

4. Quick Check:

   Root children = distinct first letters = 1 [OK]

Hint: Root children = unique first letters of words [OK]

Common Mistakes:

• Counting words instead of unique first letters
• Assuming root has no children
• Confusing shared prefixes with root children count