Trie Insert Operation in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting words into a Trie

What is the printed output of the Trie structure after inserting the words "cat", "car", and "dog" in this C++ code?

DSA C++

struct TrieNode {
    TrieNode* children[26] = {nullptr};
    bool isEnd = false;
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index])
                node->children[index] = new TrieNode();
            node = node->children[index];
        }
        node->isEnd = true;
    }

    void printTrie(TrieNode* node, std::string prefix) {
        if (node->isEnd) {
            std::cout << prefix << "\n";
        }
        for (int i = 0; i < 26; i++) {
            if (node->children[i]) {
                printTrie(node->children[i], prefix + char('a' + i));
            }
        }
    }
};

int main() {
    Trie trie;
    trie.insert("cat");
    trie.insert("car");
    trie.insert("dog");
    trie.printTrie(trie.root, "");
    return 0;
}

A "car\ndog\ncat\n"

B "cat\ncar\ndog\n"

C "dog\ncar\ncat\n"

D "car\ncat\ndog\n"

💡 Hint

Think about how the printTrie function recursively prints words in alphabetical order.

The printTrie function prints words in lexicographical order because it recursively visits children from 'a' to 'z'. The words inserted are "cat", "car", and "dog". Among "car" and "cat", "car" comes first alphabetically, then "cat", then "dog".

❓ Predict Output

intermediate

Number of nodes after inserting words in Trie

After inserting the words "apple" and "app" into an empty Trie, how many Trie nodes are created in total?

DSA C++

struct TrieNode {
    TrieNode* children[26] = {nullptr};
    bool isEnd = false;
};

class Trie {
public:
    TrieNode* root;
    int nodeCount;
    Trie() {
        root = new TrieNode();
        nodeCount = 1; // root node
    }

    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index]) {
                node->children[index] = new TrieNode();
                nodeCount++;
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    std::cout << trie.nodeCount << std::endl;
    return 0;
}

A 6

B 7

C 5

D 8

💡 Hint

Count nodes created for each unique character. Shared prefixes reuse nodes.

Inserting "apple" creates nodes for 'a', 'p', 'p', 'l', 'e' plus the root node = 6 nodes. Inserting "app" reuses 'a', 'p', 'p' nodes, so no new nodes are added. Total nodes = 6.

🔧 Debug

advanced

Identify the bug in Trie insert method

What error will occur when running this Trie insert method code snippet?

DSA C++

void insert(std::string word) {
    TrieNode* node = root;
    for (int i = 0; i <= word.length(); i++) {
        int index = word[i] - 'a';
        if (!node->children[index]) {
            node->children[index] = new TrieNode();
        }
        node = node->children[index];
    }
    node->isEnd = true;
}

A Logical error: isEnd flag never set

B Runtime error: accessing out-of-bounds index in string

C Compilation error: missing return type

D No error, code runs correctly

💡 Hint

Check the loop boundary condition carefully.

The loop runs from i = 0 to i <= word.length(), which means it accesses word[word.length()] on last iteration. This is out-of-bounds and causes runtime error.

🧠 Conceptual

advanced

Trie insert operation complexity

What is the time complexity of inserting a word of length n into a Trie?

A O(n), where n is the length of the word

B O(log n), where n is the length of the word

C O(1), constant time

D O(n^2), quadratic time

💡 Hint

Consider how many characters you process during insertion.

Insertion processes each character once, so time complexity is linear in the word length, O(n).

🚀 Application

expert

Result of inserting overlapping words in Trie

Given an empty Trie, after inserting the words "bat", "bath", and "batman", which of the following words will be recognized as complete words in the Trie?

A ["bath", "batman"]

B ["bat", "bath"]

C ["bat", "bath", "batman"]

D ["batman"]

💡 Hint

Check which nodes have the isEnd flag set after all insertions.

Each inserted word sets isEnd at its last character node. All three words are inserted fully, so all three are recognized as complete words.