31. Insert and Search in a Trie

The problem can be found at the following link: Question Link

My Approach

• For both insert and search functions, I'm using recursion to traverse the trie based on the characters of the input key.

• In the insert function, if a character node is not present in the current TrieNode, I create a new node for that character and continue the insertion.

• In the search function, I check for the existence of each character in the trie, and if the end of the key is reached and the current node is a leaf, I return true, indicating a successful search.

Time and Auxiliary Space Complexity

• Time Complexity : O(N), where N is the length of the key. In both insert and search functions, we visit each character of the key once.

• Auxiliary Space Complexity : O(N), where N is the length of the key. The space complexity is determined by the recursion stack depth.

Code (C++)

class Solution {
public:
    void insert(struct TrieNode *root, string key) {
        if (key.size() == 0) {
            root->isLeaf = true;
            return;
        }

        if (root->children[key[0] - 'a'] != NULL)
            insert(root->children[key[0] - 'a'], key.substr(1));
        else {
            root->children[key[0] - 'a'] = new TrieNode();
            insert(root->children[key[0] - 'a'], key.substr(1));
        }
    }

    bool search(struct TrieNode *root, string key) {
        if (key.size() == 0 && root->isLeaf == true)
            return true;

        if (root->children[key[0] - 'a'] != NULL)
            return search(root->children[key[0] - 'a'], key.substr(1));
        else
            return false;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.