Trie Data Structure (Prefix Tree): Insert, Search, Prefix

Type "ca" into a search box and it suggests "car", "cart" and "cat" before you finish. A spell checker suggests words that share your misspelling's beginning; a router picks the longest address prefix it has a rule for. All of these ask the same thing of a collection of strings: which stored words start with this? A trie — from re*trie*val, usually said "try" — arranges the words letter by letter in a tree, so that all words with the same beginning share one path and sit together in one subtree.

Why a hash set is not enough

A hash set answers "is car a word?" in O(L) on average. But "does any word start with ca?" has no shortcut: the prefix must be compared with every stored word.

Putting every prefix into the set answers "does any word start with p?" but not "which ones?", at a memory cost that grows with the square of the word length. A sorted list keeps the words starting with p in one block, found with two binary searches — fair when the words never change. The trie does all of it:

How a trie is stored

Each node stands for a prefix, the letters on its path from the root, and holds its children (one slot per next letter), an end flag where a stored word ends, and a pass count of the words with this prefix. The node never stores its string; its position spells it.

The end flag matters because a word can be the prefix of another: insert only "cart" and the nodes c, a, r exist, yet "car" was never inserted. The children can be an array of 26, indexed by letter − 'a' — one access per step, alphabetical order for free, most slots empty — or a hash map holding only the letters present, for any alphabet, at the cost of a hash per step.

The operations and their cost

Insert walks the word's letters from the root, creating any missing child and adding one to each pass count, then sets the end flag on the last node. Every other operation is the same walk without creating anything. Each step is one child lookup, so every operation costs O(L) for a word of length L — however many words are stored. That independence is the trie's whole promise:

1. A trie stores words letter by letter along paths from the root, so words with the same beginning share their first nodes. Each node also records whether a word ends there, because a word can be the prefix of a longer one.
2. Insert "car": the trie is empty, so c, a and r become a chain of new nodes from the root, and r is marked as the end of a word.
3. Insert "cat": the walk reuses c and a from "car", since they share the prefix "ca", then adds t and marks it as the end of a word.
4. Insert "cart": c, a and r already exist, because "car" is a prefix of "cart", so only t is new, hung below r. r keeps its own end mark, so "car" and "cart" are both words.
5. Insert "dog": no stored word starts with d, so d, o and g are all new, a separate branch from the root, and g is marked as an end. A trie only shares what words really have in common.
6. To find the words starting with "ca", walk from the root: c, then a, 2 steps however many words are stored. That node has no end mark, so "ca" is not a word itself, but everything below it starts with "ca".
7. Collecting every end mark below that node gives "car", "cart" and "cat", and the "d" branch is never touched. Inserting or walking a word of length L costs O(L); listing the matches costs the size of that one subtree.

search, startsWith and countPrefix are one walk with three different questions at the end:

1. search("car") walks c, a, r from the root, one child lookup per letter. The walk completes and r carries an end mark, so "car" is a stored word: true.
2. search("ca") walks c, a and completes too, but a has no end mark: "ca" is only the start of longer words, so the answer is false. Without end marks, every prefix would pass for a word.
3. startsWith("ca") asks less: the same walk completing is enough, mark or no mark, because some word continues through that node. The answer is true.
4. startsWith("cab") walks c, a, then finds no b child: no stored word continues that way, so the answer is false — found out after 3 lookups, however many words are stored.
5. countPrefix("car") reads the pass count of the node the walk reaches: 2 words, "car" and "cart", run through it. Insert kept the count up to date, so the answer costs only the walk: O(L).

Keeping the pass count during insert is what makes countPrefix O(L); counting on every query would cost the subtree. Autocomplete walks to the prefix, then lists its subtree with a depth-first search:

1. To list every word starting with "ca", first walk to its node: c, then a. Everything below that node starts with "ca", and nothing outside it does.
2. Search the subtree depth-first, trying children from a to z. The first end mark met is at r: write "car". Its own children come next, before its siblings.
3. Depth-first goes down before it goes sideways: the t below "car" carries an end mark, so "cart" is written before any sibling of "car".
4. That branch is finished, so the search backs up to "ca" and tries its next child, t: another end mark, so "cat" is written.
5. The subtree is done: "car", "cart" and "cat", in alphabetical order because children were tried from a to z. The 3-node branch for "dog" was never touched: the cost is the walk plus the subtree listed.

The code

A trie with a children array of 26, an end flag and a pass count, offering insert, search, startsWith, countPrefix and autocomplete:

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct TrieNode {
    TrieNode* next[26] = {};                      // one slot per letter; null when absent
    bool isEnd = false;                           // a stored word ends here
    int pass = 0;                                 // how many stored words pass through
};

class Trie {
    TrieNode root;

    void collect(TrieNode* node, string& word, vector<string>& out) {
        if (node->isEnd) out.push_back(word);
        for (int i = 0; i < 26; i++) {
            if (!node->next[i]) continue;
            word.push_back('a' + i);              // children in a..z order: words come out sorted
            collect(node->next[i], word, out);
            word.pop_back();
        }
    }

public:
    void insert(const string& word) {
        TrieNode* node = &root;
        for (char c : word) {
            if (!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
            node = node->next[c - 'a'];
            node->pass++;                         // one more word has this prefix
        }
        node->isEnd = true;
    }

    // Follows the prefix from the root; null if some letter is missing.
    TrieNode* walk(const string& prefix) {
        TrieNode* node = &root;
        for (char c : prefix) {
            node = node->next[c - 'a'];
            if (!node) return nullptr;
        }
        return node;
    }

    bool search(const string& word) { TrieNode* n = walk(word); return n && n->isEnd; }
    bool startsWith(const string& prefix) { return walk(prefix) != nullptr; }
    int countPrefix(const string& prefix) { TrieNode* n = walk(prefix); return n ? n->pass : 0; }

    vector<string> autocomplete(const string& prefix) {
        vector<string> out;
        string word = prefix;
        TrieNode* n = walk(prefix);
        if (n) collect(n, word, out);
        return out;
    }
};

int main() {
    Trie trie;
    for (string w : {"car", "cat", "cart", "dog"}) trie.insert(w);
    cout << boolalpha;
    cout << "search(car): " << trie.search("car") << "\n";
    cout << "search(ca): " << trie.search("ca") << "\n";
    cout << "startsWith(ca): " << trie.startsWith("ca") << "\n";
    cout << "startsWith(cab): " << trie.startsWith("cab") << "\n";
    for (string p : {"ca", "car", "d", "x"}) cout << "countPrefix(" << p << "): " << trie.countPrefix(p) << "\n";
    cout << "autocomplete(ca):";
    for (const string& w : trie.autocomplete("ca")) cout << " " << w;
    cout << "\n";
    return 0;
}

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class TrieNode {
        TrieNode[] next = new TrieNode[26];       // one slot per letter; null when absent
        boolean isEnd;                            // a stored word ends here
        int pass;                                 // how many stored words pass through
    }

    static class Trie {
        final TrieNode root = new TrieNode();

        void collect(TrieNode node, StringBuilder word, List<String> out) {
            if (node.isEnd) out.add(word.toString());
            for (int i = 0; i < 26; i++) {
                if (node.next[i] == null) continue;
                word.append((char) ('a' + i));    // children in a..z order: words come out sorted
                collect(node.next[i], word, out);
                word.deleteCharAt(word.length() - 1);
            }
        }

        void insert(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if (node.next[c - 'a'] == null) node.next[c - 'a'] = new TrieNode();
                node = node.next[c - 'a'];
                node.pass++;                      // one more word has this prefix
            }
            node.isEnd = true;
        }

        // Follows the prefix from the root; null if some letter is missing.
        TrieNode walk(String prefix) {
            TrieNode node = root;
            for (char c : prefix.toCharArray()) {
                node = node.next[c - 'a'];
                if (node == null) return null;
            }
            return node;
        }

        boolean search(String word) { TrieNode n = walk(word); return n != null && n.isEnd; }
        boolean startsWith(String prefix) { return walk(prefix) != null; }
        int countPrefix(String prefix) { TrieNode n = walk(prefix); return n == null ? 0 : n.pass; }

        List<String> autocomplete(String prefix) {
            List<String> out = new ArrayList<>();
            TrieNode n = walk(prefix);
            if (n != null) collect(n, new StringBuilder(prefix), out);
            return out;
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        for (String w : new String[] {"car", "cat", "cart", "dog"}) trie.insert(w);
        System.out.println("search(car): " + trie.search("car"));
        System.out.println("search(ca): " + trie.search("ca"));
        System.out.println("startsWith(ca): " + trie.startsWith("ca"));
        System.out.println("startsWith(cab): " + trie.startsWith("cab"));
        for (String p : new String[] {"ca", "car", "d", "x"}) System.out.println("countPrefix(" + p + "): " + trie.countPrefix(p));
        System.out.println("autocomplete(ca): " + String.join(" ", trie.autocomplete("ca")));
    }
}

class TrieNode:
    def __init__(self):
        self.next = [None] * 26                   # one slot per letter; None when absent
        self.is_end = False                       # a stored word ends here
        self.passes = 0                           # how many stored words pass through


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def _collect(self, node, word, out):
        if node.is_end:
            out.append("".join(word))
        for i in range(26):
            if node.next[i] is not None:
                word.append(chr(ord("a") + i))    # children in a..z order: words come out sorted
                self._collect(node.next[i], word, out)
                word.pop()

    def insert(self, word):
        node = self.root
        for ch in word:
            i = ord(ch) - ord("a")
            if node.next[i] is None:
                node.next[i] = TrieNode()
            node = node.next[i]
            node.passes += 1                      # one more word has this prefix
        node.is_end = True

    def walk(self, prefix):
        """Follow the prefix from the root; None if some letter is missing."""
        node = self.root
        for ch in prefix:
            node = node.next[ord(ch) - ord("a")]
            if node is None:
                return None
        return node

    def search(self, word):
        node = self.walk(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self.walk(prefix) is not None

    def count_prefix(self, prefix):
        node = self.walk(prefix)
        return 0 if node is None else node.passes

    def autocomplete(self, prefix):
        out = []
        node = self.walk(prefix)
        if node is not None:
            self._collect(node, list(prefix), out)
        return out


def text(flag):
    return "true" if flag else "false"


trie = Trie()
for w in ["car", "cat", "cart", "dog"]:
    trie.insert(w)
print("search(car):", text(trie.search("car")))
print("search(ca):", text(trie.search("ca")))
print("startsWith(ca):", text(trie.starts_with("ca")))
print("startsWith(cab):", text(trie.starts_with("cab")))
for p in ["ca", "car", "d", "x"]:
    print(f"countPrefix({p}):", trie.count_prefix(p))
print("autocomplete(ca):", *trie.autocomplete("ca"))

class TrieNode {
  constructor() {
    this.next = new Array(26).fill(null); // one slot per letter; null when absent
    this.isEnd = false; // a stored word ends here
    this.pass = 0; // how many stored words pass through
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  collect(node, word, out) {
    if (node.isEnd) out.push(word);
    for (let i = 0; i < 26; i++) {
      // children in a..z order: words come out sorted
      if (node.next[i] !== null) this.collect(node.next[i], word + String.fromCharCode(97 + i), out);
    }
  }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      const i = ch.charCodeAt(0) - 97;
      if (node.next[i] === null) node.next[i] = new TrieNode();
      node = node.next[i];
      node.pass++; // one more word has this prefix
    }
    node.isEnd = true;
  }

  // Follows the prefix from the root; null if some letter is missing.
  walk(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      node = node.next[ch.charCodeAt(0) - 97];
      if (node === null) return null;
    }
    return node;
  }

  search(word) { const n = this.walk(word); return n !== null && n.isEnd; }
  startsWith(prefix) { return this.walk(prefix) !== null; }
  countPrefix(prefix) { const n = this.walk(prefix); return n === null ? 0 : n.pass; }

  autocomplete(prefix) {
    const out = [];
    const n = this.walk(prefix);
    if (n !== null) this.collect(n, prefix, out);
    return out;
  }
}

const trie = new Trie();
for (const w of ["car", "cat", "cart", "dog"]) trie.insert(w);
console.log(`search(car): ${trie.search("car")}`);
console.log(`search(ca): ${trie.search("ca")}`);
console.log(`startsWith(ca): ${trie.startsWith("ca")}`);
console.log(`startsWith(cab): ${trie.startsWith("cab")}`);
for (const p of ["ca", "car", "d", "x"]) console.log(`countPrefix(${p}): ${trie.countPrefix(p)}`);
console.log(`autocomplete(ca): ${trie.autocomplete("ca").join(" ")}`);

search(car): true
search(ca): false
startsWith(ca): true
startsWith(cab): false
countPrefix(ca): 3
countPrefix(car): 2
countPrefix(d): 1
countPrefix(x): 0
autocomplete(ca): car cart cat

Walking the trie along a text

The trie's most useful trick in problems is not a single lookup but a walk alongside another string. Stand at position i of a text and walk the trie with the text's letters: every end flag passed is a dictionary word starting at i, and a missing child means no stored word continues, so you stop. One walk finds every word starting at i, in time bounded by the longest word.

1. Find every dictionary word that starts at position 0 of "cartoon" with one walk: step through the text's letters and the trie together, from the root.
2. "c": there is a child for c at the root, so step down. No end mark yet, so "c" is not a word on its own.
3. "a": there is a child for a below "c", so step down. No end mark yet, so "ca" is not a word on its own.
4. "r" leads to a node with an end mark: "car" is a dictionary word starting at position 0. Note it and keep walking — a longer word may follow.
5. "t" leads to a node with an end mark: "cart" is a dictionary word starting at position 0. Note it and keep walking — a longer word may follow.
6. "o": the trie has no o below "cart", so no stored word continues this way and the walk stops after 4 letters. One walk found "car" and "cart", in time bounded by the longest word, not the text.

• Replace Words stops at the first end flag: the shortest root.
• Extra Characters in a String and Word Break run dynamic programming over positions, with one trie walk from each.
• Word Search II moves down the trie in step with a backtracking search of a grid, abandoning a path the moment the trie has no child for the next letter.
• Sum of Prefix Scores of Strings adds up the pass counts along each word.

Memory, and when a set is simpler

A trie has at most one node per character inserted. But with a children array every node carries 26 references, 208 bytes in C++ on a 64-bit machine, so 100,000 ten-letter words with little sharing can need around 200 MB. The ways out: children in a hash map; one flat array of node indices, next[node][letter], the contest style; or no trie at all — if you only ask whether whole words are present, a hash set is simpler and smaller. Reach for the trie for prefix questions, counts, listings or a walk along a text.

The XOR trie: maximum XOR of two numbers

With the alphabet {0, 1}, a trie finds the largest a XOR b over all pairs of an array without checking every pair. Insert every number into a binary trie, one bit per level from the highest bit down; then, for each number, walk down taking the opposite bit whenever that child exists.

1. Each number is stored as a path of 5 bits, highest first: 0 to the left, 1 to the right. To find 5's best partner (5 = 00101₂), walk down and take the bit opposite to 5's whenever that child exists — that bit of the XOR is then 1.
2. Bit 4: 5 has 0, so a 1 here makes this XOR bit 1, worth 16 — more than all the lower bits together, 15. The 1 branch exists, so take it: only 25 is left on this path.
3. Bit 3: 5 has 0, so a 1 here makes this XOR bit 1, worth 8 — more than all the lower bits together, 7. The 1 branch exists, so take it: only 25 is left on this path.
4. Bit 2: 5 has 1, so a 0 here makes this XOR bit 1, worth 4 — more than all the lower bits together, 3. The 0 branch exists, so take it: only 25 is left on this path.
5. Bit 1: 5 has 0 and wants 1, but the only number left, 25, has 0 here: no choice, so this XOR bit is 0.
6. Bit 0: 5 has 1 and wants 0, but the only number left, 25, has 1 here: no choice, so this XOR bit is 0.
7. The walk ends at 25: 5 XOR 25 = 11100₂ = 28, the largest XOR 5 can make with any number here. One walk of 5 steps per number makes the whole search O(n × B) instead of O(n²) pairs.

Why is the greedy choice right? A 1 in bit b is worth 2ᵇ, more than all the lower bits together (2ᵇ − 1), so a 1 in the highest possible bit beats any combination below it — which is also why the bits must go in highest first. Maximum XOR of Two Numbers in an Array is exactly this; more bit tricks are in bit manipulation.

#include <iostream>
#include <vector>
using namespace std;

const int HIGH_BIT = 30;                          // non-negative ints fit in bits 30..0

struct BitNode {
    BitNode* child[2] = {nullptr, nullptr};
    int value = 0;                                // the number whose path ends here
};

void insert(BitNode* root, int x) {
    BitNode* node = root;
    for (int b = HIGH_BIT; b >= 0; b--) {         // highest bit first
        int bit = (x >> b) & 1;
        if (!node->child[bit]) node->child[bit] = new BitNode();
        node = node->child[bit];
    }
    node->value = x;
}

// The stored number whose XOR with x is largest.
int bestPartner(BitNode* root, int x) {
    BitNode* node = root;
    for (int b = HIGH_BIT; b >= 0; b--) {
        int bit = (x >> b) & 1;
        if (node->child[1 - bit]) node = node->child[1 - bit];  // opposite bit: a 1 in the XOR
        else node = node->child[bit];
    }
    return node->value;
}

int main() {
    vector<int> nums = {3, 10, 5, 25, 2, 8};
    BitNode* root = new BitNode();
    for (int x : nums) insert(root, x);
    int best = -1, a = 0, b = 0;
    for (int x : nums) {
        int y = bestPartner(root, x);
        if ((x ^ y) > best) { best = x ^ y; a = x; b = y; }
    }
    cout << "Numbers:";
    for (int x : nums) cout << " " << x;
    cout << "\n";
    cout << "Maximum XOR: " << a << " XOR " << b << " = " << best << "\n";
    return 0;
}

public class Main {
    static final int HIGH_BIT = 30;               // non-negative ints fit in bits 30..0

    static class BitNode {
        BitNode[] child = new BitNode[2];
        int value;                                // the number whose path ends here
    }

    static void insert(BitNode root, int x) {
        BitNode node = root;
        for (int b = HIGH_BIT; b >= 0; b--) {     // highest bit first
            int bit = (x >> b) & 1;
            if (node.child[bit] == null) node.child[bit] = new BitNode();
            node = node.child[bit];
        }
        node.value = x;
    }

    // The stored number whose XOR with x is largest.
    static int bestPartner(BitNode root, int x) {
        BitNode node = root;
        for (int b = HIGH_BIT; b >= 0; b--) {
            int bit = (x >> b) & 1;
            if (node.child[1 - bit] != null) node = node.child[1 - bit];  // opposite bit: a 1 in the XOR
            else node = node.child[bit];
        }
        return node.value;
    }

    public static void main(String[] args) {
        int[] nums = {3, 10, 5, 25, 2, 8};
        BitNode root = new BitNode();
        for (int x : nums) insert(root, x);
        int best = -1, a = 0, b = 0;
        for (int x : nums) {
            int y = bestPartner(root, x);
            if ((x ^ y) > best) { best = x ^ y; a = x; b = y; }
        }
        StringBuilder line = new StringBuilder("Numbers:");
        for (int x : nums) line.append(" ").append(x);
        System.out.println(line);
        System.out.println("Maximum XOR: " + a + " XOR " + b + " = " + best);
    }
}

HIGH_BIT = 30                                     # non-negative ints fit in bits 30..0


class BitNode:
    def __init__(self):
        self.child = [None, None]
        self.value = 0                            # the number whose path ends here


def insert(root, x):
    node = root
    for b in range(HIGH_BIT, -1, -1):             # highest bit first
        bit = (x >> b) & 1
        if node.child[bit] is None:
            node.child[bit] = BitNode()
        node = node.child[bit]
    node.value = x


def best_partner(root, x):
    """The stored number whose XOR with x is largest."""
    node = root
    for b in range(HIGH_BIT, -1, -1):
        bit = (x >> b) & 1
        if node.child[1 - bit] is not None:
            node = node.child[1 - bit]            # opposite bit: a 1 in the XOR
        else:
            node = node.child[bit]
    return node.value


nums = [3, 10, 5, 25, 2, 8]
root = BitNode()
for x in nums:
    insert(root, x)
best, a, b = -1, 0, 0
for x in nums:
    y = best_partner(root, x)
    if x ^ y > best:
        best, a, b = x ^ y, x, y
print("Numbers:", *nums)
print(f"Maximum XOR: {a} XOR {b} = {best}")

const HIGH_BIT = 30; // non-negative ints fit in bits 30..0

class BitNode {
  constructor() {
    this.child = [null, null];
    this.value = 0; // the number whose path ends here
  }
}

function insert(root, x) {
  let node = root;
  for (let b = HIGH_BIT; b >= 0; b--) { // highest bit first
    const bit = (x >> b) & 1;
    if (node.child[bit] === null) node.child[bit] = new BitNode();
    node = node.child[bit];
  }
  node.value = x;
}

// The stored number whose XOR with x is largest.
function bestPartner(root, x) {
  let node = root;
  for (let b = HIGH_BIT; b >= 0; b--) {
    const bit = (x >> b) & 1;
    if (node.child[1 - bit] !== null) node = node.child[1 - bit]; // opposite bit: a 1 in the XOR
    else node = node.child[bit];
  }
  return node.value;
}

const nums = [3, 10, 5, 25, 2, 8];
const root = new BitNode();
for (const x of nums) insert(root, x);
let best = -1, a = 0, b = 0;
for (const x of nums) {
  const y = bestPartner(root, x);
  if ((x ^ y) > best) { best = x ^ y; a = x; b = y; }
}
console.log(`Numbers: ${nums.join(" ")}`);
console.log(`Maximum XOR: ${a} XOR ${b} = ${best}`);

Numbers: 3 10 5 25 2 8
Maximum XOR: 5 XOR 25 = 28

Every number is inserted before any search, so a walk never meets a dead end.

Time and space complexity

How to recognise a trie problem

• The statement is about prefixes: "starts with", "is a prefix of", "shortest root", autocomplete.
• A dictionary must be matched against every position of a text, or against paths in a grid.
• You must count the words sharing a prefix, or sum something over all prefixes.
• The words must come out in alphabetical order as you build or search.
• The maximum or minimum XOR of a pair: a binary trie over the bits.

Common mistakes

• Forgetting the end flag: without it, "car" is found after inserting only "cart". search checks the flag; startsWith does not.
• Counting on every query instead of keeping a pass count.
• Assuming lower-case letters: c − 'a' breaks on capitals, digits or spaces. Check the alphabet, or use a map.
• Inserting bits lowest first: the XOR greedy needs the highest bit decided first.
• Creating nodes in a lookup: only insert creates nodes; a search that does fills the trie with junk.
• Running out of memory with 26 references per node on a large dictionary.

Practice in this order

1. Longest Common Prefix: walk down while there is exactly one child and no word ends.
2. Longest Word in Dictionary: only paths flagged at every node count.
3. Replace Words: stop at the first end flag.
4. Short Encoding of Words: insert the words reversed, so shared suffixes share nodes.
5. Maximum XOR of Two Numbers in an Array: the binary trie and its greedy walk.
6. Extra Characters in a String: dynamic programming with a trie walk from each position.
7. Sum of Prefix Scores of Strings: pass counts summed along each word.
8. Word Search II: a trie steering a backtracking search through a grid.

The trie problem list has every trie problem in the catalogue. That completes the tree-shaped structures of this stage; the road continues with matrices and grids, where the first two-dimensional walks are the same depth-first and breadth-first traversals you used on trees.