Trie — Insert & Search

What is a Trie?

A prefix tree where each node has up to 26 children (for lowercase English). Words share common prefixes, saving space. The root is empty. A node is marked as end of word when a complete word ends there.

Operations

Insert: walk char by char, create nodes as needed, mark end
Search: walk char by char, check if path exists AND ends at a word mark
StartsWith: walk char by char, check if path exists (no end check needed)

🔧 Live Trie Playground

Word:

Inserted Words

No words yet

Traversal Path

Insert or search a word

Trie Structure

Insert words to build the trie, then search to test lookups.

C++ — Trie Implementation

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

class Trie {
    TrieNode* root = new TrieNode();
public:
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int i = c - 'a';
            if (!node->children[i])
                node->children[i] = new TrieNode();
            node = node->children[i];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int i = c - 'a';
            if (!node->children[i]) return false;
            node = node->children[i];
        }
        return node->isEnd;
    }

    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int i = c - 'a';
            if (!node->children[i]) return false;
            node = node->children[i];
        }
        return true;
    }
};

Complexity

Insert / Search

O(L)

L = length of the word. One node per character.

Space

O(N × L × 26)

Worst case: N words of length L, 26 children per node.

📝 Notes

▼