Trie Insert Operation in DSA C - Build from Scratch

Trie Insert Operation

📖 Scenario: Imagine you are building a simple dictionary app that stores words for quick lookup. To do this efficiently, you use a Trie data structure, which organizes words by their letters.

🎯 Goal: You will create a Trie node structure, then write code to insert words into the Trie. Finally, you will print the Trie's structure to see the inserted words.

📋 What You'll Learn

Define a Trie node struct with an array for children and a boolean to mark end of word

Create a root Trie node

Write a function to insert a word into the Trie

Insert given words into the Trie

Print the Trie's structure showing inserted words

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete systems, spell checkers, and IP routing to quickly find words or prefixes.

💼 Career

Understanding Trie insertions helps in roles involving text processing, search engines, and efficient data retrieval.

1

Create the Trie node structure and root node

Define a struct called TrieNode with an array children of size 26 for pointers to TrieNode, and an int called isEndOfWord. Then create a function getNode() that allocates memory for a new TrieNode, initializes isEndOfWord to 0 and all children pointers to NULL. Finally, create a TrieNode pointer called root and set it to the result of getNode().

DSA C

// Define TrieNode struct and getNode function
// Create root node
// Your code here

Hint

Use malloc to allocate memory for a new node. Initialize isEndOfWord to 0 and all children pointers to NULL.

2

Add a helper function to convert characters to index

Create a function called charToIndex that takes a char parameter c and returns an int index by subtracting 'a' from c. This will convert lowercase letters to indices 0 to 25.

DSA C

#include 
#include 

#define ALPHABET_SIZE 26

typedef struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    int isEndOfWord;
} TrieNode;

TrieNode* getNode(void) {
    TrieNode* pNode = (TrieNode*)malloc(sizeof(TrieNode));
    pNode->isEndOfWord = 0;
    for (int i = 0; i children[i] = NULL;
    }
    return pNode;
}

int charToIndex(char c) {
    // Your code here
}

int main() {
    TrieNode* root = getNode();
    return 0;
}

Hint

Subtract the character 'a' from the input character to get the index.

3

Write the insert function to add words to the Trie

Write a function called insert that takes a TrieNode* called root and a const char* called key. Use a pointer pCrawl starting at root. For each character in key, convert it to an index using charToIndex. If the child at that index is NULL, create a new node with getNode(). Move pCrawl to the child node. After the loop, mark pCrawl->isEndOfWord as 1.

DSA C

#include 
#include 

#define ALPHABET_SIZE 26

typedef struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    int isEndOfWord;
} TrieNode;

TrieNode* getNode(void) {
    TrieNode* pNode = (TrieNode*)malloc(sizeof(TrieNode));
    pNode->isEndOfWord = 0;
    for (int i = 0; i children[i] = NULL;
    }
    return pNode;
}

int charToIndex(char c) {
    return c - 'a';
}

void insert(TrieNode* root, const char* key) {
    // Your code here
}

int main() {
    TrieNode* root = getNode();
    return 0;
}

Hint

Use a loop to go through each character of the word. Create new nodes if needed. Mark the last node as end of word.

4

Insert words and print the Trie's structure

In main(), insert the words "hello", "world", and "hi" into the Trie using the insert function. Then write a function printTrie that takes a TrieNode* and a char array word[] with an int level. It recursively prints all words stored in the Trie by traversing children. Call printTrie(root, word, 0) to print all inserted words, one per line.

DSA C

#include 
#include 

#define ALPHABET_SIZE 26

typedef struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    int isEndOfWord;
} TrieNode;

TrieNode* getNode(void) {
    TrieNode* pNode = (TrieNode*)malloc(sizeof(TrieNode));
    pNode->isEndOfWord = 0;
    for (int i = 0; i children[i] = NULL;
    }
    return pNode;
}

int charToIndex(char c) {
    return c - 'a';
}

void insert(TrieNode* root, const char* key) {
    TrieNode* pCrawl = root;
    for (int level = 0; key[level] != '\0'; level++) {
        int index = charToIndex(key[level]);
        if (pCrawl->children[index] == NULL) {
            pCrawl->children[index] = getNode();
        }
        pCrawl = pCrawl->children[index];
    }
    pCrawl->isEndOfWord = 1;
}

void printTrie(TrieNode* root, char word[], int level) {
    // Your code here
}

int main() {
    TrieNode* root = getNode();
    insert(root, "hello");
    insert(root, "world");
    insert(root, "hi");
    // Your code here
    return 0;
}

Hint

Use recursion to explore all children. When isEndOfWord is 1, print the current word built so far.

Practice

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

easy

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

B. To delete a word from the Trie

C. To search for a word in the Trie

D. To count the number of words in the Trie

Solution

1. Step 1: Understand the insert operation

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

2. Step 2: Differentiate from other operations

   Deleting removes words, searching checks presence, counting totals words. Insert specifically adds words.

3. Final Answer:

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

4. Quick Check:

   Insert = Add word [OK]

Hint: Insert means adding word letters step-by-step [OK]

Common Mistakes:

• Confusing insert with search or delete
• Thinking insert counts words
• Assuming insert removes words

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

easy

A. typedef struct TrieNode { char* word; struct TrieNode* children[26]; } TrieNode;

B. typedef struct TrieNode { int data; struct TrieNode* next; } TrieNode;

C. typedef struct TrieNode { struct TrieNode* children[26]; bool isEndOfWord; } TrieNode;

D. typedef struct TrieNode { struct TrieNode* left; struct TrieNode* right; } TrieNode;

Solution

1. Step 1: Identify Trie node components

   A Trie node has an array of pointers for children (26 letters) and a boolean to mark word end.

2. Step 2: Match with options

   typedef struct TrieNode { struct TrieNode* children[26]; bool isEndOfWord; } TrieNode; matches this structure. Others describe linked list or binary tree nodes, not Trie nodes.

3. Final Answer:

   typedef struct TrieNode { struct TrieNode* children[26]; bool isEndOfWord; } TrieNode; -> Option C

4. Quick Check:

   Trie node = children array + end flag [OK]

Hint: Trie nodes have 26 children pointers and end-of-word flag [OK]

Common Mistakes:

• Using linked list node structure instead of array
• Confusing Trie with binary tree node
• Missing end-of-word boolean

3. What will be the output of the following C code snippet after inserting the word "cat" into an empty Trie and checking the isEndOfWord flag at the last node?

TrieNode* root = createNode();
insert(root, "cat");
bool flag = root->children['c' - 'a']->children['a' - 'a']->children['t' - 'a']->isEndOfWord;
printf("%d", flag);

medium

A. 0

B. Runtime error

C. Compilation error

D. 1

Solution

1. Step 1: Insert "cat" into Trie

   Each character creates or uses existing nodes. The last character 't' node's isEndOfWord is set to true (1).

2. Step 2: Check isEndOfWord flag

   Accessing the node for 't' and printing isEndOfWord prints 1 because the word ends there.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   Inserted word end flag = 1 [OK]

Hint: End node flag is set to true after insert [OK]

Common Mistakes:

• Assuming isEndOfWord is 0 after insert
• Indexing children incorrectly
• Forgetting to set isEndOfWord during insert

4. Consider the following buggy insert function for a Trie in C:

void insert(TrieNode* root, const char* word) {
    TrieNode* node = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (node->children[index] == NULL) {
            node->children[index] = malloc(sizeof(TrieNode));
        }
        node = node->children[index];
    }
    node->isEndOfWord = true;
}

What is the main bug in this code?

medium

A. New nodes are not initialized, leading to garbage values

B. The loop condition is incorrect and may cause infinite loop

C. The isEndOfWord flag is set too early

D. The root pointer is not updated after insertion

Solution

1. Step 1: Analyze node allocation

   New nodes are allocated with malloc but not initialized, so children pointers and isEndOfWord have garbage values.

2. Step 2: Consequences of uninitialized nodes

   Uninitialized children can cause incorrect behavior or crashes during further insert/search operations.

3. Final Answer:

   New nodes are not initialized, leading to garbage values -> Option A

4. Quick Check:

   Missing initialization = bug [OK]

Hint: Always initialize new Trie nodes after malloc [OK]

Common Mistakes:

• Ignoring initialization of new nodes
• Assuming malloc zeros memory
• Confusing loop condition correctness

5. You want to insert multiple words into a Trie and then count how many words start with the prefix "pre". Which modification to the Trie insert operation helps achieve this efficiently?

hard

A. Store the entire word at each node instead of characters

B. Add a counter in each node that increments every time a word passes through it during insertion

C. Only mark isEndOfWord without any counters

D. Use a linked list instead of an array for children nodes

Solution

1. Step 1: Understand prefix counting

   To count words with a prefix, each node can keep a count of how many words pass through it.

2. Step 2: Modify insert to update counters

   During insertion, increment the counter at each node visited. Then prefix count is the counter at prefix's last node.

3. Final Answer:

   Add a counter in each node that increments every time a word passes through it during insertion -> Option B

4. Quick Check:

   Prefix count = node counters [OK]

Hint: Use counters in nodes to track prefix occurrences [OK]

Common Mistakes:

• Not using counters, making prefix count slow
• Storing full words at nodes wastes space
• Using linked list slows access