Trie Node Design and Initialization in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Node Initialization

What is the output of this C code that initializes a Trie node and prints its initial state?

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ALPHABET_SIZE 26

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

TrieNode* getNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}

int main() {
    TrieNode* root = getNode();
    int count = 0;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (root->children[i] == NULL) {
            count++;
        }
    }
    printf("isEndOfWord: %d, NULL children count: %d\n", root->isEndOfWord, count);
    free(root);
    return 0;
}

A isEndOfWord: 0, NULL children count: 26

B isEndOfWord: 1, NULL children count: 0

C isEndOfWord: 0, NULL children count: 0

D isEndOfWord: 1, NULL children count: 26

💡 Hint

Check how the node's isEndOfWord is initialized and how children pointers are set.

The Trie node is initialized with isEndOfWord set to false (0) and all children pointers set to NULL. Since ALPHABET_SIZE is 26, all children are NULL, so count is 26.

🧠 Conceptual

intermediate

Understanding Trie Node Children Array

In a Trie node design in C, why do we use an array of pointers of size 26 for children?

A To store the ASCII values of characters in the node

B To store the frequency of each character in the node

C To represent each lowercase English alphabet letter as a possible child node

D To keep track of the parent nodes for backtracking

💡 Hint

Think about how Trie nodes represent letters in words.

Each index in the children array corresponds to a letter 'a' to 'z'. This allows quick access to child nodes representing each letter.

🔧 Debug

advanced

Identify the Bug in Trie Node Initialization

What error will this C code cause when initializing a Trie node?

DSA C

#include <stdlib.h>
#include <stdbool.h>
#define ALPHABET_SIZE 26

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

TrieNode* getNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}

A No error, code runs correctly

B Buffer overflow due to out-of-bounds array access

C Compilation error due to missing header

D Segmentation fault at malloc

💡 Hint

Check the loop boundary condition for children initialization.

The loop runs from 0 to ALPHABET_SIZE inclusive, but children array indices go from 0 to ALPHABET_SIZE-1. Accessing children[26] causes buffer overflow.

❓ Predict Output

advanced

Output After Inserting a Word in Trie

What is the output of this C code after inserting the word "cat" into the Trie and checking the isEndOfWord flag?

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ALPHABET_SIZE 26

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

TrieNode* getNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}

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

int main() {
    TrieNode* root = getNode();
    insert(root, "cat");
    printf("isEndOfWord at 't' node: %d\n", root->children['c' - 'a']->children['a' - 'a']->children['t' - 'a']->isEndOfWord);
    free(root);
    return 0;
}

A isEndOfWord at 't' node: 1

B isEndOfWord at 't' node: 0

C Segmentation fault

D Compilation error

💡 Hint

Check how the insert function sets the isEndOfWord flag at the last character node.

The insert function sets isEndOfWord to true at the node representing 't' in "cat". So printing it outputs 1.

🧠 Conceptual

expert

Memory Usage Optimization in Trie Node Design

Which approach best reduces memory usage in a Trie node design for English lowercase letters while maintaining efficient search?

A Store all words in a flat array instead of a Trie

B Use a linked list to store children nodes dynamically

C Use a fixed array of 26 pointers for children in every node

D Use a hash map or dictionary to store only existing children nodes

💡 Hint

Think about storing only necessary children to save space.

Using a hash map or dictionary stores only existing children, reducing memory compared to fixed arrays with many NULLs, while keeping search efficient.

Practice

1. What is the primary purpose of a Trie node in a Trie data structure?

easy

A. To store the length of the string

B. To store integer values for sorting

C. To hold pointers to parent nodes only

D. To store children nodes representing characters of strings

Solution

1. Step 1: Understand Trie node role

   A Trie node represents a character and links to children nodes for next characters in strings.

2. Step 2: Identify correct purpose

   It stores children nodes to build paths for strings, not integer values or lengths.

3. Final Answer:

   To store children nodes representing characters of strings -> Option D

4. Quick Check:

   Trie node = children nodes [OK]

Hint: Trie nodes link characters as children nodes [OK]

Common Mistakes:

• Thinking Trie nodes store whole strings
• Confusing with storing string length
• Assuming nodes only point to parents

2. Which of the following is the correct way to declare a Trie node struct in C with 26 children pointers and a boolean flag for end of word?

easy

A. typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode;

B. typedef struct TrieNode { struct TrieNode children[26]; int isEndOfWord; } TrieNode;

C. typedef struct TrieNode { struct TrieNode* children; int isEndOfWord; } TrieNode;

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

Solution

1. Step 1: Check children declaration

   Children must be pointers to TrieNode, so use struct TrieNode* children[26];

2. Step 2: Check end of word flag type

   Using int for boolean is common in C; bool requires stdbool.h and is less common.

3. Final Answer:

   typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode; -> Option A

4. Quick Check:

   Children pointers array + int flag = typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode; [OK]

Hint: Use pointers array for children and int for boolean in C [OK]

Common Mistakes:

• Declaring children as struct array instead of pointers
• Using bool without including stdbool.h
• Declaring children as single pointer instead of array

3. Given the following code snippet, what will be the output?

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

TrieNode* getNode() {
  TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
  node->isEndOfWord = 0;
  for (int i = 0; i < 26; i++)
    node->children[i] = NULL;
  return node;
}

int main() {
  TrieNode* root = getNode();
  printf("%d\n", root->isEndOfWord);
  printf("%p\n", root->children[0]);
  return 0;
}

medium

A. 1
0x0 (NULL pointer address)

B. Garbage value
Garbage pointer

C. 0
0x0 (NULL pointer address)

D. 0
Non-null pointer address

Solution

1. Step 1: Analyze getNode initialization

   isEndOfWord is set to 0 explicitly; children array elements set to NULL (0).

2. Step 2: Check main output

   Printing isEndOfWord prints 0; printing children[0] prints NULL pointer (0x0).

3. Final Answer:

   0 0x0 (NULL pointer address) -> Option C

4. Quick Check:

   Initialized zero and NULL = 0 0x0 (NULL pointer address) [OK]

Hint: Uninitialized pointers cause garbage; here all set NULL [OK]

Common Mistakes:

• Assuming uninitialized pointers have zero value
• Confusing isEndOfWord default value
• Expecting children pointers to have non-null addresses

4. Identify the error in the following Trie node initialization code and select the fix:

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

TrieNode* getNode() {
  TrieNode* node = malloc(sizeof(TrieNode));
  node->isEndOfWord = 0;
  for (int i = 0; i <= 26; i++)
    node->children[i] = NULL;
  return node;
}

medium

A. Loop condition should be i < 26 to avoid out-of-bounds access

B. Missing cast for malloc return value

C. isEndOfWord should be initialized to 1

D. children array size should be 27

Solution

1. Step 1: Check loop bounds

   Loop runs from i = 0 to i <= 26, which means 27 iterations, but children array size is 26, causing out-of-bounds access.

2. Step 2: Identify correct fix

   Loop should run i < 26 to stay within array bounds and avoid memory errors.

3. Final Answer:

   Loop condition should be i < 26 to avoid out-of-bounds access -> Option A

4. Quick Check:

   Array size 26 means max index 25 [OK]

Hint: Array size 26 means loop i < 26, not <= 26 [OK]

Common Mistakes:

• Using <= instead of < in loops
• Ignoring array bounds causing runtime errors
• Assuming malloc cast is mandatory in C

5. You want to initialize a Trie node that supports lowercase English letters and also store the frequency of words ending at that node. Which of the following struct definitions correctly extends the basic Trie node design?

hard

A. typedef struct TrieNode { struct TrieNode* children[26]; bool isEndOfWord; int frequency; } TrieNode;

B. typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; int frequency; } TrieNode;

C. typedef struct TrieNode { struct TrieNode* children[26]; int frequency; } TrieNode;

D. typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; int* frequency; } TrieNode;

Solution

1. Step 1: Check children and end flag

   Children array of pointers size 26 is correct; isEndOfWord as int is standard in C.

2. Step 2: Add frequency field correctly

   Frequency should be an int to count occurrences; pointer to int is unnecessary complexity.

3. Final Answer:

   typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; int frequency; } TrieNode; -> Option B

4. Quick Check:

   Use int for frequency and isEndOfWord [OK]

Hint: Add int frequency field directly, keep isEndOfWord as int [OK]

Common Mistakes:

• Using pointer for frequency unnecessarily
• Omitting isEndOfWord flag
• Using bool without stdbool.h