Trie Insert Operation in DSA C#

Mental Model

A trie stores words by branching letters step-by-step, sharing common prefixes to save space.

Analogy: Imagine a tree of roads where each letter is a street sign; inserting a word means walking or building streets letter by letter until the word is complete.

root
 ↓
[ ]
Each bracket is a node with possible letter branches.

Dry Run Walkthrough

Input: Insert words: "cat", then "car" into an empty trie

Goal: Build the trie so it stores both words sharing the prefix 'ca'

Step 1: Insert 'c' from 'cat' at root since no children exist

root -> c
[c node]

Why: Start building the path for the first word from the root

Step 2: Insert 'a' after 'c' node

root -> c -> a
[c node -> a node]

Why: Continue the word by adding next letter

Step 3: Insert 't' after 'a' node and mark end of word

root -> c -> a -> t*
[t node marked as word end]

Why: Complete the first word by marking the last letter node

Step 4: Insert 'c' for second word 'car' - already exists, move to 'a'

root -> c -> a -> t*
[c node -> a node -> t* node]

Why: Reuse existing prefix nodes to save space

Step 5: Insert 'r' after 'a' node for 'car' and mark end of word

root -> c -> a -> t*
               ↘ r*
[t and r nodes marked as word ends]

Why: Add new branch for different ending letter and mark word end

Result:

root -> c -> a -> t*
               ↘ r*
Both 'cat' and 'car' stored sharing prefix 'ca'

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class TrieNode
{
    public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
    public bool IsWordEnd = false;
}

class Trie
{
    private TrieNode root = new TrieNode();

    public void Insert(string word)
    {
        TrieNode current = root;
        foreach (char ch in word)
        {
            if (!current.Children.ContainsKey(ch))
            {
                current.Children[ch] = new TrieNode();
            }
            current = current.Children[ch]; // advance to next node
        }
        current.IsWordEnd = true; // mark end of word
    }

    public void PrintTrie()
    {
        PrintNode(root, "root");
    }

    private void PrintNode(TrieNode node, string prefix)
    {
        foreach (var kvp in node.Children)
        {
            string endMark = kvp.Value.IsWordEnd ? "*" : "";
            Console.WriteLine($"{prefix} -> {kvp.Key}{endMark}");
            PrintNode(kvp.Value, prefix + kvp.Key);
        }
    }
}

class Program
{
    static void Main()
    {
        Trie trie = new Trie();
        trie.Insert("cat");
        trie.Insert("car");
        trie.PrintTrie();
    }
}

foreach (char ch in word)

iterate each letter to insert step-by-step

if (!current.Children.ContainsKey(ch))

check if letter node exists to reuse or create new

current.Children[ch] = new TrieNode();

create new node for letter if missing

current = current.Children[ch];

advance current pointer to next letter node

current.IsWordEnd = true;

mark last node as end of a valid word

Output

root -> c

rootc -> a

rootca -> t*

rootca -> r*

Complexity Analysis

Time: O(m) because we process each letter of the word once during insertion

Space: O(m) for new nodes created if letters are not shared with existing words

vs Alternative: Compared to storing words in a list, trie insertion is faster for prefix queries but uses more memory for nodes

Edge Cases

Insert empty string

No nodes added, root remains unchanged

DSA C#

foreach (char ch in word)

Insert word already in trie

No new nodes created, end node marked again

DSA C#

if (!current.Children.ContainsKey(ch))

Insert word with prefix already present

Shared prefix nodes reused, only new suffix nodes added

DSA C#

if (!current.Children.ContainsKey(ch))

When to Use This Pattern

When you need to store many words sharing prefixes and quickly check or insert them, use a trie insert operation to build a prefix tree efficiently.

Common Mistakes

Mistake: Not marking the last node as end of word, causing search failures
Fix: Always set current.IsWordEnd = true after inserting all letters

Mistake: Creating new nodes even if letter node already exists, wasting memory
Fix: Check if node exists before creating new one using ContainsKey

Summary

Inserts words letter by letter into a tree structure sharing prefixes.

Use when storing many words to save space and enable fast prefix queries.

The key is to reuse existing letter nodes and mark the end of each word.

Practice

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

easy

A. To count the number of words stored in the Trie

B. To delete a word from the Trie

C. To search for a word in the Trie

D. To add a word character by character into the Trie

Solution

1. Step 1: Understand the Insert operation

   The Insert operation adds each character of a word into the Trie one by one, creating nodes if they don't exist.

2. Step 2: Compare with other operations

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

3. Final Answer:

   To add a word character by character into the Trie -> Option D

4. Quick Check:

   Insert = Add word step-by-step [OK]

Hint: Insert means adding word letters one by one [OK]

Common Mistakes:

• Confusing Insert with Delete or Search
• Thinking Insert counts words
• Assuming Insert removes nodes

2. Which of the following is the correct way to declare a Trie node class in C# for insertion?

easy

A. public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsEndOfWord = false; }

B. public class TrieNode { public List<int> Children; public bool IsEndOfWord; }

C. public class TrieNode { public int[] Children = new int[26]; public bool IsEndOfWord; }

D. public class TrieNode { public string Children; public bool IsEndOfWord; }

Solution

1. Step 1: Identify correct data structure for children

   Trie nodes use a dictionary mapping characters to child nodes for flexible branching.

2. Step 2: Check class members

   public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsEndOfWord = false; } uses Dictionary and a boolean flag for word end, which is standard.

3. Final Answer:

   public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsEndOfWord = false; } -> Option A

4. Quick Check:

   Children dictionary + end flag = public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsEndOfWord = false; } [OK]

Hint: Use Dictionary for children in C# Trie nodes [OK]

Common Mistakes:

• Using List<int> instead of dictionary for children
• Using int array without node references
• Using string instead of node references

3. Consider the following C# code inserting the word "cat" into an empty Trie. What will be the state of the root node's children after insertion?

Trie trie = new Trie();
trie.Insert("cat");
var childrenKeys = trie.Root.Children.Keys.ToList();
childrenKeys.Sort();
Console.WriteLine(string.Join(",", childrenKeys));

medium

A. "t"

B. "a"

C. "c"

D. "cat"

Solution

1. Step 1: Insert "cat" character by character

   First character 'c' is added as a child of root node.

2. Step 2: Check root's children keys

   Only 'c' is directly under root; 'a' and 't' are children of subsequent nodes.

3. Final Answer:

   "c" -> Option C

4. Quick Check:

   Root children keys = first letter only [OK]

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

Common Mistakes:

• Assuming all letters appear at root children
• Confusing nested children with root children
• Printing full word as a key

4. The following C# code attempts to insert the word "dog" into a Trie but has a bug. What is the error?

public void Insert(string word) {
    var node = Root;
    foreach (char c in word) {
        if (!node.Children.ContainsKey(c)) {
            node.Children[c] = new TrieNode();
        }
        node = node.Children[c];
    }
    node.IsEndOfWord = false;
}

medium

A. The IsEndOfWord flag should be set to true after insertion

B. The foreach loop should iterate backwards

C. Children dictionary should be cleared before insertion

D. Root node should be reinitialized inside the method

Solution

1. Step 1: Analyze IsEndOfWord assignment

   After inserting all characters, IsEndOfWord marks the end of a valid word and must be true.

2. Step 2: Identify the bug

   Code sets IsEndOfWord to false, which incorrectly marks the word as not complete.

3. Final Answer:

   The IsEndOfWord flag should be set to true after insertion -> Option A

4. Quick Check:

   End flag = true after insert [OK]

Hint: Set IsEndOfWord = true after inserting full word [OK]

Common Mistakes:

• Setting IsEndOfWord to false instead of true
• Reinitializing root unnecessarily
• Clearing children during insert

5. You want to insert multiple words into a Trie and then check if the word "bat" exists. Which sequence of operations correctly inserts "bat", "ball", and "batman" and marks them properly in C#?

hard

A. Insert "bat", Insert "ball", Insert "batman"; set IsEndOfWord true at root node

B. Insert "bat", Insert "ball", Insert "batman"; set IsEndOfWord true only at last character of each word

C. Insert "bat", Insert "ball", Insert "batman"; set IsEndOfWord true for all nodes

D. Insert "bat", Insert "ball", Insert "batman"; set IsEndOfWord false for all nodes

Solution

1. Step 1: Insert each word fully

   Insert each word character by character, creating nodes as needed.

2. Step 2: Mark end of each word

   Set IsEndOfWord = true only at the last character node of each inserted word to mark valid words.

3. Final Answer:

   Insert "bat", Insert "ball", Insert "batman"; set IsEndOfWord true only at last character of each word -> Option B

4. Quick Check:

   End flag true only at word ends [OK]

Hint: Mark end flag true only at last letter of each word [OK]

Common Mistakes:

• Marking root or all nodes as end of word
• Not marking end of word nodes
• Setting end flag false after insert