Assignment: Tries | DSA in C++ - Software Development PDF Download

Multiple Choice Questions (MCQs)

Q.1. Which of the following data structure is suitable for implementing a Trie?
(a) Array
(b) Linked List
(c) Stack
(d) Tree

Ans. (d)

Q.2. What is the time complexity for searching a word in a Trie?

(a) O(n)
(b) O(log n)
(c) O(m)
(d) O(1)

Ans. (c)

Q.3.  is the space complexity of a Trie?
(a) O(n)
(b) O(m)
(c) O(log n)
(d) O(1)

Ans. (a)

Q.4. The process of adding a new word to a Trie is called:
(a) Insertion
(b) Deletion
(c) Searching
(d) Traversal

Ans. (a)

Q.5. Which of the following operations is used to delete a word from a Trie?
(a) remove()
(b) delete()
(c) erase()
(d) destroy()

Ans. (c)

High Order Thinking Questions (HOTS)

Q.1. Design a Trie data structure to store the following words: "cat," "car," "bat," "bar," and "can."

The Trie for the given words:

root

/ |

c b a

/ |

a a n

| |

t r

Q.2. Write a function to search for a specific key in a Trie. Explain the algorithm and its time complexity.

Algorithm for searching a key in a Trie:

• Start from the root node.
• For each character in the key, check if the child node corresponding to that character exists.
• If the child node exists, move to the next character.
• If any character is not found or the last character is not marked as the end of a word, the key is not present in the Trie.
• If all characters are found and the last character is marked as the end of a word, the key is present in the Trie.
• The time complexity of the search operation is O(m), where m is the length of the key.

Q.3. Implement a function to delete a key from a Trie. Provide the code and explain the steps involved in the deletion process.

Steps for deleting a key from a Trie:

• Start from the root node and traverse through the Trie to find the node corresponding to the last character of the key.
• Remove the mark indicating the end of the key from the last character node.
• If the last character node has no other children, delete the node and recursively delete its parent if it also has no other children.
• Repeat the above steps until the key is fully deleted.
• The time complexity of the deletion operation depends on the length of the key and the structure of the Trie.

Q.4. Can a Trie be used to efficiently find the k most frequent words from a given set of strings? Justify your answer.

No, a Trie alone cannot efficiently find the k most frequent words from a given set of strings. To find the k most frequent words, additional data structures like a heap or a priority queue can be used to store and retrieve the top k frequent words based on their frequencies.

Q.5. How would you modify a Trie data structure to support efficient wildcard pattern matching? Explain the modifications required.

To support efficient wildcard pattern matching in a Trie, modifications can be made by introducing a special character to represent a wildcard. This special character can match any other character during pattern matching. Additionally, modifications need to be made in the search algorithm to handle wildcard characters appropriately.

Fill in the Blanks

1. A Trie is a ____________  data structure that is commonly used for storing ____________.

A Trie is a tree-based data structure that is commonly used for storing strings.

2. In a Trie, each node represents a ____________ of a ____________.

In a Trie, each node represents a character of a string.

3. The root node of a Trie has an ____________ character.

The root node of a Trie has an empty character.

4. search operation in a Trie starts from the ____________ node.

The search operation in a Trie starts from the root node.

5. The time complexity for searching a key in a Trie is ____________.

The time complexity for searching a key in a Trie is O(m), where m is the length of the key.

True or False

1. Tries are efficient for storing large amounts of data. (True/False)

True

2. The height of a Trie depends on the number of keys stored in it. (True/False)

False

3. Deletion in a Trie requires updating the pointers and removing unnecessary nodes. (True/False)

True

4. Tries are commonly used for implementing dictionaries and spell-checking applications. (True/False)

True

5. A Trie can store only lowercase alphabets. (True/False)

False

Hands-On Questions

Q.1. Implement a Trie data structure in C++ and write functions for insertion, search, and deletion.

// Trie Node

struct TrieNode {

    bool isEndOfWord;

    TrieNode* children[26]; // Assuming only lowercase English letters

    TrieNode() {

        isEndOfWord = false;

        for (int i = 0; i < 26; i++) {

            children[i] = nullptr;

        }

    }

};

class Trie {

private:

    TrieNode* root;

public:

    Trie() {

        root = new TrieNode();

    }

    void insert(string word) {

        TrieNode* curr = root;

        for (char ch : word) {

            int index = ch - 'a';

            if (curr->children[index] == nullptr) {

                curr->children[index] = new TrieNode();

            }

            curr = curr->children[index];

        }

        curr->isEndOfWord = true;

    }

    bool search(string word) {

        TrieNode* curr = root;

        for (char ch : word) {

            int index = ch - 'a';

            if (curr->children[index] == nullptr) {

                return false;

            }

            curr = curr->children[index];

        }

        return curr != nullptr && curr->isEndOfWord;

    }

    bool startsWith(string prefix) {

        TrieNode* curr = root;

        for (char ch : prefix) {

            int index = ch - 'a';

            if (curr->children[index] == nullptr) {

                return false;

            }

            curr = curr->children[index];

        }

        return curr != nullptr;

    }

    // Helper function to check if a TrieNode has any children

    bool hasChildren(TrieNode* node) {

        for (int i = 0; i < 26; i++) {

            if (node->children[i] != nullptr) {

                return true;

            }

        }

        return false;

    }

    bool removeHelper(TrieNode* curr, string word, int index) {

        if (index == word.length()) {

            if (!curr->isEndOfWord) {

                return false; // Word not found

            }

            curr->isEndOfWord = false;

            return !hasChildren(curr); // Check if curr has any children, if not, it can be deleted

        }

        int ch = word[index] - 'a';

        if (curr->children[ch] == nullptr) {

            return false; // Word not found

        }

        bool shouldDeleteNode = removeHelper(curr->children[ch], word, index + 1);

        if (shouldDeleteNode) {

            delete curr->children[ch];

            curr->children[ch] = nullptr;

            return !curr->isEndOfWord && !hasChildren(curr); // Check if curr has any children or is not the end of a word, if not, it can be deleted

        }

        return false;

    }

    bool remove(string word) {

        return removeHelper(root, word, 0);

    }

};

Q.2. Given a list of strings, implement a function to find the longest common prefix using a Trie.

string longestCommonPrefix(vector<string>& strs) {

    if (strs.empty()) {

        return "";

    }

    Trie trie;

    for (const string& word : strs) {

        trie.insert(word);

    }

    string prefix = "";

    TrieNode* curr = trie.root;

    while (trie.hasChildren(curr) && !curr->isEndOfWord) {

        for (int i = 0; i < 26; i++) {

            if (curr->children[i] != nullptr) {

                curr = curr->children[i];

                prefix += ('a' + i);

                break;

            }

        }

    }

    return prefix;

}

Q.3. Design a phone directory using a Trie data structure. Include functionalities for adding contacts, searching contacts, and deleting contacts.

struct Contact {

    string name;

    string number;

};

class PhoneDirectory {

private:

    Trie contacts;

public:

    void addContact(const Contact& contact) {

        contacts.insert(contact.number);

    }

    bool searchContact(const string& number) {

        return contacts.search(number);

    }

    bool deleteContact(const string& number) {

        return contacts.remove(number);

    }

};

Q.4. Implement a function to perform weighted prefix search in a Trie. The weight of each word represents its frequency.

struct WeightedWord {

    string word;

    int weight;

};

class WeightedPrefixSearch {

private:

    Trie weightedWords;

public:

    void insert(const WeightedWord& weightedWord) {

        weightedWords.insert(weightedWord.word);

        // Store the weight associated with the word in the Trie node (additional field can be added to TrieNode)

        // This can be used to retrieve the weight of a word during prefix search

    }

    vector<string> searchByPrefix(const string& prefix) {

        TrieNode* curr = weightedWords.root;

        vector<string> result;

        // Traverse to the Trie node corresponding to the prefix

        for (char ch : prefix) {

            int index = ch - 'a';

            if (curr->children[index] == nullptr) {

                return result; // Prefix not found

            }

            curr = curr->children[index];

        }

      // Perform depth-first search to retrieve all words with the given prefix

        searchByPrefixHelper(curr, prefix, result);

        return result;

    }

private:

    void searchByPrefixHelper(TrieNode* node, string currentWord, vector<string>& result) {

        if (node->isEndOfWord) {

            result.push_back(currentWord);

        }

        for (int i = 0; i < 26; i++) {

            if (node->children[i] != nullptr) {

                char ch = 'a' + i;

                searchByPrefixHelper(node->children[i], currentWord + ch, result);

            }

        }

    }

};

Q.5. Implement the Boggle game using a Trie data structure to efficiently find valid words on the board. Provide a step-by-step explanation of the algorithm.

The Boggle game algorithm using a Trie can be outlined as follows:

• Build a Trie using a dictionary of valid words.
• Traverse the Boggle board using depth-first search (DFS) or backtracking.
• For each cell in the board, check if any valid word can be formed starting from that cell.
• Perform the following steps for each cell:
  • Start with the current cell as the initial node in the Trie.
  • Explore all valid neighboring cells (up, down, left, right, and diagonal).
  • If the current prefix exists in the Trie, check if it is a valid word.
  • If it is a valid word, add it to the result set.
  • If the current prefix is a prefix of any valid word in the Trie, continue the exploration.
  • If the current prefix is not a prefix of any valid word, backtrack to the previous cell.
• Repeat steps 4a-4f for all cells on the board.
• Return the set of valid words found during the traversal.

The implementation of the Boggle game using a Trie involves combining the Trie structure with the DFS or backtracking algorithm to explore all possible paths on the board and find valid words efficiently.