Project: Text Autocomplete with a Trie

In this project you’ll build a text-autocomplete engine — type "ca" and it returns ["cat", "car", "card"]. The right tool is a Trie (a prefix tree): a tree where each edge is a character, so every path from the root spells a prefix. Tries make “find all words starting with X” fast and natural, which is exactly what autocomplete needs. If Tries are new, read Tries: Introduction first.

What you’ll build

Two operations:

insert(word) — add a word to the dictionary.
suggest(prefix) — return every stored word that begins with prefix.

It exercises tree construction, tree traversal (DFS), and string building — the core skills behind real autocomplete, spell-checkers, and IP routing tables.

Why a Trie and not a list

With a plain list of n words each up to length L, every suggest call scans all of them: O(n·L). A Trie shares common prefixes, so finding the prefix node is just O(L) — independent of how many words you stored — and then you only walk the subtree under that node.

Operation	List scan	Trie
insert	O(L)	O(L)
suggest (locate prefix)	O(n·L)	O(L)
suggest (collect k results)	—	O(k·L)

Step 1 — the node and inserting words

Each node holds a map from a character to a child node, plus a flag marking whether a complete word ends here. To insert, walk character by character, creating nodes as needed, and set isWord on the last node.

Step 2 — suggesting completions

To suggest, first walk down the prefix. If any character has no child, there are no matches — return empty. Otherwise you’ve landed on the node representing the prefix; run a DFS through its subtree, and every node flagged isWord is a completion. Build the output string by appending each edge’s character as you descend.

Here is the complete engine — insert plus prefix suggestions:

#include <unordered_map>
#include <memory>
#include <string>
#include <vector>

class Autocomplete {
    struct TrieNode {
        std::unordered_map<char, std::unique_ptr<TrieNode>> children;
        bool isWord = false;
    };
    TrieNode root;

    void dfs(TrieNode* node, std::string& buf, std::vector<std::string>& out) {
        if (node->isWord) out.push_back(buf);
        for (auto& [c, child] : node->children) {
            buf.push_back(c);
            dfs(child.get(), buf, out);
            buf.pop_back();
        }
    }
public:
    void insert(const std::string& word) {
        TrieNode* node = &root;
        for (char c : word) {
            if (!node->children.count(c))
                node->children[c] = std::make_unique<TrieNode>();
            node = node->children[c].get();
        }
        node->isWord = true;
    }

    std::vector<std::string> suggest(const std::string& prefix) {
        std::vector<std::string> out;
        TrieNode* node = &root;
        for (char c : prefix) {
            auto it = node->children.find(c);
            if (it == node->children.end()) return out; // no match
            node = it->second.get();
        }
        std::string buf = prefix;
        dfs(node, buf, out);
        return out;
    }
};

import java.util.*;

class Autocomplete {
    private static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isWord = false;
    }
    private final TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray())
            node = node.children.computeIfAbsent(c, k -> new TrieNode());
        node.isWord = true;
    }

    List<String> suggest(String prefix) {
        List<String> out = new ArrayList<>();
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            node = node.children.get(c);
            if (node == null) return out; // no match
        }
        dfs(node, new StringBuilder(prefix), out);
        return out;
    }

    private void dfs(TrieNode node, StringBuilder buf, List<String> out) {
        if (node.isWord) out.add(buf.toString());
        for (Map.Entry<Character, TrieNode> e : node.children.entrySet()) {
            buf.append(e.getKey());
            dfs(e.getValue(), buf, out);
            buf.deleteCharAt(buf.length() - 1);
        }
    }
}

class Autocomplete {
  constructor() {
    this.root = { children: new Map(), isWord: false };
  }

  insert(word) {
    let node = this.root;
    for (const c of word) {
      if (!node.children.has(c))
        node.children.set(c, { children: new Map(), isWord: false });
      node = node.children.get(c);
    }
    node.isWord = true;
  }

  suggest(prefix) {
    const out = [];
    let node = this.root;
    for (const c of prefix) {
      node = node.children.get(c);
      if (!node) return out; // no match
    }
    this.#dfs(node, prefix, out);
    return out;
  }

  #dfs(node, buf, out) {
    if (node.isWord) out.push(buf);
    for (const [c, child] of node.children)
      this.#dfs(child, buf + c, out);
  }
}

class Autocomplete:
    def __init__(self):
        self.root = {"children": {}, "is_word": False}

    def insert(self, word):
        node = self.root
        for c in word:
            node = node["children"].setdefault(c, {"children": {}, "is_word": False})
        node["is_word"] = True

    def suggest(self, prefix):
        out = []
        node = self.root
        for c in prefix:
            node = node["children"].get(c)
            if node is None:
                return out  # no match
        self._dfs(node, prefix, out)
        return out

    def _dfs(self, node, buf, out):
        if node["is_word"]:
            out.append(buf)
        for c, child in node["children"].items():
            self._dfs(child, buf + c, out)

Trying it out

Insert "cat", "car", "card", "dog", then call suggest("ca") — you get cat, car, and card in some order, while suggest("z") returns an empty list.

Gotcha: suggest("") (empty prefix) returns every word, because the empty string is a prefix of everything. That’s usually the behavior you want, but cap the result count in production so a single keystroke doesn’t return the whole dictionary.

Complexity

insert: O(L) time for a word of length L.
suggest: O(L) to reach the prefix node, then O(k·L) to collect k matches.
space: O(total characters across all words) in the worst case (no shared prefixes).

Going deeper: To rank suggestions, store a frequency or score on each isWord node and return the top results with a heap. For typo tolerance, blend in edit distance. The Trie stays the backbone either way.

Next project: an LRU cache.