Trie Data Structure from Scratch (2026)

Published: February 24, 2026 | Category: Dsa | Reading time: ~15 min

A Trie (prefix tree) is a tree-like data structure that stores strings character by character. Each node represents a single character, and paths from the root to leaf nodes represent complete strings. Tries enable fast prefix-based searches, autocomplete, spell checking, and IP routing table lookups.

Unlike hash tables, tries can search for strings with common prefixes efficiently and support ordered iteration. The time complexity for insert, search, and delete is O(m) where m is the length of the word, independent of the number of stored strings.

📖 Table of Contents

Insert and Search in Trie
Autocomplete Implementation

Insert and Search in Trie

Insert traverses character by character from the root, creating new nodes as needed, and marks the last node as an end-of-word node. Search follows the same path and returns true only if the current node exists and is marked as an end-of-word.

class TrieNode {
public:
  TrieNode* children[26];
  bool isEnd;
  TrieNode() : isEnd(false) {
    fill(begin(children), end(children), nullptr);
  }
};

void insert(TrieNode* root, string word) {
  TrieNode* cur = root;
  for (char c : word) {
    int idx = c - 'a';
    if (!cur->children[idx]) cur->children[idx] = new TrieNode();
    cur = cur->children[idx];
  }
  cur->isEnd = true;
}

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

Autocomplete Implementation

Autocomplete finds all words with a given prefix. Traverse to the node representing the prefix, then perform a DFS from that node collecting words along each path. The output is sorted lexicographically due to the natural traversal order of children.

# Python: Autocomplete with Trie
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def autocomplete(root, prefix):
    node = root
    for ch in prefix:
        if ch not in node.children: return []
        node = node.children[ch]
    result = []
    def dfs(n, path):
        if n.is_end: result.append(prefix + path)
        for c, child in sorted(n.children.items()):
            dfs(child, path + c)
    dfs(node, "")
    return result

Frequently Asked Questions

What is the space complexity of a Trie?

In the worst case, a Trie uses O(ALPHABET_SIZE × total_characters) space. Compressed tries (radix trees) and ternary search trees offer more memory-efficient alternatives.

Can a Trie handle Unicode strings?

Yes, but the node's children array becomes impractically large. Hash-based children (dictionaries) are used instead of fixed arrays for Unicode alphabets like UTF-8.

Originally published on Ayodhyyya. Last updated June 1, 2026.