DSA

Implement Trie

Trie problem — solution with code and analysis.

August 8, 2026

Practice Link

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Design#

Each TrieNode stores an array of 26 child pointers (one per lowercase letter) and an isEnd flag marking whether a complete word ends at that node. To insert a word, traverse character by character creating nodes as needed and mark isEnd = true at the last character. For search, traverse the same path and check that isEnd is set at the final node. For prefix search, just confirm the path exists without checking isEnd. All operations run in O(m) where m is the length of the word/prefix — independent of how many words are stored.

Implement the Trie class:

Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise

cpp

class TrieNode{
public:
    bool isEnd;
    TrieNode* children[26];

    TrieNode(){
        isEnd = false;
        for(int i=0;i<26;i++)
            children[i] = NULL;
    }
};

class Trie {
public:
    TrieNode* root;
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode* curr = root;
        for(int i=0;i<word.length();i++){
            int idx = word[i]- 'a';
            if(curr->children[idx] == NULL)
                curr->children[idx] = new TrieNode();
            curr = curr->children[idx];
        }
        curr->isEnd = true;
    }
    
    bool search(string word) {
        TrieNode* curr = root;
        for(int i=0;i<word.length();i++){
            int idx = word[i]- 'a';
            if(curr->children[idx] == NULL)
                return false;
            curr = curr->children[idx];
        }
        return curr->isEnd;
    }
    
    bool startsWith(string prefix) {
        TrieNode* curr = root;
        for(int i=0;i<prefix.length();i++){
            int idx = prefix[i]- 'a';
            if(curr->children[idx] == NULL)
                return false;
            curr = curr->children[idx];
        }
        return true;
    }
};

Complexities#

Operation	Time Complexity	Space Complexity
Insert	O(m)	O(n*m)
Search	O(m)	O(1)
PrefixSearch	O(m)	O(1)

DSAImplement Trie - IITrie problem — solution with code and analysis.DSALFU CacheStacks & Queues. Time O(1).DSAWord Search IITrie. Time O(m×k×4^L), Space O(L).

Design#

Complexities#

Related articles