Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › DSA

Trie (Prefix Tree)

A trie stores strings one character per level. Words that share a prefix share the same path, so prefix questions are very fast.

insert: "cat", "car", "dog"
            (root)
            /    \
           c      d
           |      |
           a      o
          / \     |
         t*  r*   g*        * = end of a word

Node and operations

struct TrieNode {
    TrieNode* child[26] = {};      // for lowercase a–z
    bool isEnd = false;
    int prefixCount = 0;           // how many words pass through here (optional)
};

class Trie {
    TrieNode* root = new TrieNode();
public:
    void insert(const string& w) {
        TrieNode* cur = root;
        for (char c : w) {
            int i = c - 'a';
            if (!cur->child[i]) cur->child[i] = new TrieNode();
            cur = cur->child[i];
            cur->prefixCount++;
        }
        cur->isEnd = true;
    }
    bool search(const string& w) {           // whole word
        TrieNode* n = walk(w);
        return n && n->isEnd;
    }
    bool startsWith(const string& p) {       // any word with this prefix
        return walk(p) != nullptr;
    }
    int countPrefix(const string& p) {
        TrieNode* n = walk(p);
        return n ? n->prefixCount : 0;
    }
private:
    TrieNode* walk(const string& s) {
        TrieNode* cur = root;
        for (char c : s) {
            cur = cur->child[c - 'a'];
            if (!cur) return nullptr;
        }
        return cur;
    }
};

Complexity

Operation Time
Insert / search / startsWith O(L) — L = length of the word, independent of how many words are stored
Space O(total characters × alphabet size) in the worst case

For a big or unknown alphabet, use unordered_map<char, TrieNode*> instead of a fixed array (less memory, a bit slower).

Trie vs hash set

Hash set Trie
Exact lookup O(L) average O(L)
Prefix search ("words starting with ca") O(n · L) — check every word O(L)
Sorted output no yes (DFS in letter order)
Memory lower higher

Uses

Deleting a word

Clear isEnd; optionally remove nodes on the way back up if they have no children and are not the end of another word (decrement prefixCount).

Classic problems

Problem Idea
Implement Trie insert / search / startsWith
Design add and search words (with . wildcard) DFS on .
Word search II trie + grid DFS
Longest word in dictionary words whose every prefix is a word
Replace words shortest root prefix
Maximum XOR of two numbers binary trie
Search suggestions system trie + DFS (or sorting + binary search)

Practise in the Trie section.

Interview one-liners

More DSA notes