Trie Data Structure: Implementation, Interview Problems & Memory Trade-offs

The trie is one of the few data structures where the interview question is often simply "implement it". That makes it a free win if you prepare, and a painful 20 minutes if you do not. Beyond implementation, tries are the key to a handful of problems that are otherwise too slow, most famously Word Search II, which is near the top of most "hard problems asked at FAANG" lists.

This guide covers the structure, a clean implementation in Java, C++ and Python, the core problem patterns with code, the binary XOR trie, and the memory discussion interviewers use to separate strong candidates.

What a Trie Is: A Tree Keyed by Characters

The name comes from retrieval (usually pronounced "try" to avoid confusion with "tree"). Each node represents a prefix. The root is the empty prefix. Each edge is labelled with a character, and a node's children are the prefixes one character longer. A boolean isEnd marks nodes where a complete word ends.

The diagram shows the two things that make a trie useful. Shared prefixes are stored once ("ap" serves app, apple and apt). And "is there any word starting with ba?" is answered by walking two edges, without looking at any words at all.

Note the marker on the second p: "app" is a word and a prefix of "apple". That is why isEnd is a flag on the node, not a property of leaves. Forgetting this is the most common trie bug.

Trie vs Hash Set vs Sorted List

An honest observation for interviews: for a static dictionary and only prefix existence checks, a sorted array with binary search is often simpler and more memory-efficient. Tries win when the dictionary changes, when many searches share prefixes, or when you need incremental, character-by-character matching (typing in a search box, walking a grid).

Implement a Trie (LeetCode 208) in Java, C++ and Python

class Trie {
    private static class Node {
        Node[] next = new Node[26];
        boolean isEnd;
    }

    private final Node root = new Node();

    public void insert(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            int c = word.charAt(i) - 'a';
            if (cur.next[c] == null) cur.next[c] = new Node();
            cur = cur.next[c];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        Node node = walk(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }

    private Node walk(String s) {
        Node cur = root;
        for (int i = 0; i < s.length() && cur != null; i++) {
            cur = cur.next[s.charAt(i) - 'a'];
        }
        return cur;
    }
}

class Trie {
    struct Node {
        Node* next[26] = {};
        bool isEnd = false;
    };
    Node* root = new Node();

    Node* walk(const string& s) const {
        Node* cur = root;
        for (char ch : s) {
            cur = cur->next[ch - 'a'];
            if (!cur) return nullptr;
        }
        return cur;
    }

    static void destroy(Node* n) {
        if (!n) return;
        for (Node* child : n->next) destroy(child);
        delete n;
    }

public:
    ~Trie() { destroy(root); }

    void insert(const string& word) {
        Node* cur = root;
        for (char ch : word) {
            int c = ch - 'a';
            if (!cur->next[c]) cur->next[c] = new Node();
            cur = cur->next[c];
        }
        cur->isEnd = true;
    }
    bool search(const string& word) const {
        Node* n = walk(word);
        return n && n->isEnd;
    }
    bool startsWith(const string& prefix) const {
        return walk(prefix) != nullptr;
    }
};

class TrieNode:
    __slots__ = ("children", "is_end")

    def __init__(self):
        self.children = {}
        self.is_end = False


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

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def _walk(self, s):
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

Design choices worth saying out loud: the Java and C++ versions use a fixed array of 26 children (fast, lowercase-only, memory-hungry); the Python version uses a dict (any alphabet, smaller for sparse nodes). __slots__ in Python cuts per-node memory noticeably by removing the per-instance __dict__. The shared walk helper keeps search and startsWith to one line each, which interviewers appreciate.

Deletion

Deletion is a common follow-up. Unset isEnd at the word's last node; then, walking back up, delete any node that has no children and is not the end of another word. A recursive helper that returns "can this child be removed?" is the cleanest version. Many implementations also keep a count (number of words passing through each node), which makes deletion and "how many words have this prefix?" both trivial: decrement counts on the path and drop a child when its count reaches zero.

Dry Run: Insert and Search

1. insert("app"). root has no 'a': create it. 'a' has no 'p': create. That 'p' has no 'p': create. Mark the last node isEnd. Three nodes created.
2. insert("apple"). Walk a → p → p (existing, no allocation). Create 'l', then 'e'. Mark 'e' isEnd. Two nodes created: the shared prefix cost nothing.
3. search("appl"). Walk a → p → p → l: node exists, but isEnd is false. Return false.
4. startsWith("appl"). Same walk, node exists. Return true.
5. search("apz"). Walk a → p, then 'z' is missing. Return false after three steps, no matter how many words are stored.

Wildcard Search: Design Add and Search Words (211)

Words can be searched with . matching any single letter. Exact characters follow one edge; a dot branches into all existing children. Use DFS over (node, index).

class WordDictionary {
    private static class Node {
        Node[] next = new Node[26];
        boolean isEnd;
    }
    private final Node root = new Node();

    public void addWord(String word) {
        Node cur = root;
        for (char ch : word.toCharArray()) {
            int c = ch - 'a';
            if (cur.next[c] == null) cur.next[c] = new Node();
            cur = cur.next[c];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        return dfs(word, 0, root);
    }

    private boolean dfs(String w, int i, Node node) {
        if (node == null) return false;
        if (i == w.length()) return node.isEnd;
        char ch = w.charAt(i);
        if (ch != '.') return dfs(w, i + 1, node.next[ch - 'a']);
        for (Node child : node.next) {
            if (child != null && dfs(w, i + 1, child)) return true;
        }
        return false;
    }
}

Worst case for a pattern of all dots is O(26^L) in theory, but it is bounded by the number of trie nodes at each depth, so in practice it is O(number of nodes). Without a trie, a hash set would need to try 26^k concrete strings for k dots. A useful optimisation when words have many lengths: keep a separate trie (or set) per word length, since a pattern can only match words of its own length.

Word Search II (212): Trie + Backtracking

Given an m × n board of letters and a list of words, return all words that can be formed by adjacent (4-directional) cells without reusing a cell. Running Word Search I backtracking once per word costs O(W · m · n · 4 · 3^L−1) and times out with thousands of words.

The trie fix: insert all words into one trie. Start a DFS from every cell, carrying the current trie node. Move to a neighbour only if the trie has a child for that letter. When you reach a node that ends a word, record it. One DFS now searches for all words at once, and it stops the moment the path is not a prefix of anything.

def find_words(board, words):
    root = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node["$"] = w                       # store the word at its end node

    R, C = len(board), len(board[0])
    found = []

    def dfs(r, c, parent):
        ch = board[r][c]
        node = parent[ch]
        word = node.pop("$", None)          # pop: report each word once
        if word:
            found.append(word)
        board[r][c] = "#"                   # mark visited
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < R and 0 <= nc < C and board[nr][nc] in node:
                dfs(nr, nc, node)
        board[r][c] = ch                    # restore
        if not node:                        # prune exhausted branch
            parent.pop(ch)

    for r in range(R):
        for c in range(C):
            if board[r][c] in root:
                dfs(r, c, root)
    return found

class Solution {
    private static class Node {
        Node[] next = new Node[26];
        String word;                        // non-null at word ends
    }

    public List<String> findWords(char[][] board, String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node cur = root;
            for (char ch : w.toCharArray()) {
                int c = ch - 'a';
                if (cur.next[c] == null) cur.next[c] = new Node();
                cur = cur.next[c];
            }
            cur.word = w;
        }
        List<String> res = new ArrayList<>();
        for (int r = 0; r < board.length; r++)
            for (int c = 0; c < board[0].length; c++)
                dfs(board, r, c, root, res);
        return res;
    }

    private void dfs(char[][] b, int r, int c, Node parent, List<String> res) {
        if (r < 0 || r >= b.length || c < 0 || c >= b[0].length) return;
        char ch = b[r][c];
        if (ch == '#' || parent.next[ch - 'a'] == null) return;
        Node node = parent.next[ch - 'a'];
        if (node.word != null) {
            res.add(node.word);
            node.word = null;               // avoid duplicates
        }
        b[r][c] = '#';
        dfs(b, r + 1, c, node, res);
        dfs(b, r - 1, c, node, res);
        dfs(b, r, c + 1, node, res);
        dfs(b, r, c - 1, node, res);
        b[r][c] = ch;
    }
}

Three optimisations interviewers look for:

1. Store the word at the end node instead of rebuilding it from the path: no string concatenation inside the DFS.
2. Remove found words (null the word / pop the marker) so each is reported once without a result set.
3. Prune empty branches (the Python version deletes a child once its subtree has no words left), so later DFS calls stop earlier. On boards full of repeated letters, this is the difference between passing and timing out.

Complexity: O(m · n · 4 · 3^L−1) in the worst case, where L is the maximum word length (first step has 4 directions, later steps 3 since you cannot go back), plus O(S) to build the trie. Crucially it no longer multiplies by the number of words.

Autocomplete: Search Suggestions System (1268) and Top-K by Frequency

Search Suggestions System: after each typed character, return up to three lexicographically smallest products with that prefix. With a trie, store at every node a list of up to three suggestions while inserting the products in sorted order. Then each query is one step down the trie.

def suggested_products(products, search_word):
    products.sort()
    root = {}
    for p in products:
        node = root
        for ch in p:
            node = node.setdefault(ch, {"#": []})
            if len(node["#"]) < 3:
                node["#"].append(p)         # sorted insertion keeps the 3 smallest
    res, node = [], root
    for ch in search_word:
        node = node.get(ch) if node else None
        res.append(node["#"] if node else [])
    return res

The sorted-array alternative is equally good here: sort once, and for each prefix binary-search the first product ≥ prefix and check the next three. Mention both; it shows you are choosing tools rather than reaching for a trie by reflex.

Ranking by popularity

Real autocomplete ranks by frequency, not alphabet. Design Search Autocomplete System (642) stores counts at word ends and, for a prefix, collects all words in the subtree and returns the top 3 by (−count, word). The production approach caches the top-K list at each node so queries are O(prefix length), at the cost of updating every node on the path when counts change. That trade-off (precomputed top-K at nodes, offline rebuilds, sharding by prefix, caching hot prefixes at the CDN) is the heart of the search autocomplete system design interview.

Other Trie Problems: Replace Words, Longest Word, Word Break

• Replace Words (648): insert roots, then for each word walk the trie and stop at the first isEnd: that is the shortest root. O(total characters).
• Longest Word in Dictionary (720): a word counts only if every prefix is also a word. DFS the trie, descending only into children with isEnd set; track the longest (ties by lexicographic order, which DFS in child order gives naturally).
• Word Break (139): the standard DP checks whether s[j:i] is in a set for every j < i. With a trie, from each reachable start index walk forward through the trie and mark every isEnd position as reachable; you stop as soon as the trie has no child. See LeetCode 139 explained for the DP baseline.
• Palindrome Pairs (336): a hard problem that uses a trie of reversed words; good to recognise, rarely asked fully.
• Stream of Characters (1032): insert words reversed; for each new character, walk the trie over the stream suffix backwards. Bounded by the maximum word length per query.
• Prefix and suffix counts: store a count per node; "how many words start with p?" is one walk.

For string techniques that compete with tries (hashing, KMP, rolling hash), see string interview problem patterns.

XOR Trie: Maximum XOR of Two Numbers (421)

Store each integer as a 31- or 32-bit binary string, most significant bit first, in a trie with two children per node. For a query x, the maximum XOR partner is found greedily: at each bit, try to go to the child with the opposite bit (that bit of the XOR becomes 1). Higher bits dominate all lower bits combined (2^k > 2^k−1 + ... + 1), so the greedy choice from the top is optimal.

class XorTrie {
    vector<array<int, 2>> nxt;              // node pool: index-based children
public:
    static const int BITS = 31;               // values fit in 31 bits (non-negative int)
    XorTrie() { nxt.push_back({0, 0}); }      // node 0 = root; 0 also means "absent"

    void insert(int x) {
        int cur = 0;
        for (int b = BITS - 1; b >= 0; b--) {
            int bit = (x >> b) & 1;
            if (!nxt[cur][bit]) {
                nxt[cur][bit] = nxt.size();
                nxt.push_back({0, 0});
            }
            cur = nxt[cur][bit];
        }
    }

    int maxXor(int x) const {                 // requires at least one inserted value
        int cur = 0, res = 0;
        for (int b = BITS - 1; b >= 0; b--) {
            int bit = (x >> b) & 1;
            if (nxt[cur][bit ^ 1]) {
                res |= (1 << b);
                cur = nxt[cur][bit ^ 1];
            } else {
                cur = nxt[cur][bit];
            }
        }
        return res;
    }
};

int findMaximumXOR(vector<int>& nums) {
    XorTrie t;
    int best = 0;
    for (int x : nums) {
        t.insert(x);
        best = max(best, t.maxXor(x));
    }
    return best;
}

def find_maximum_xor(nums):
    BITS = max(nums).bit_length()
    root = {}
    best = 0
    for x in nums:
        node = root                          # insert x
        for b in range(BITS - 1, -1, -1):
            node = node.setdefault((x >> b) & 1, {})
        node, cur = root, 0                  # query best partner for x
        for b in range(BITS - 1, -1, -1):
            bit = (x >> b) & 1
            if 1 - bit in node:
                cur |= 1 << b
                node = node[1 - bit]
            else:
                node = node[bit]
        best = max(best, cur)
    return best

Inserting x before querying guarantees the trie is non-empty (x XOR x = 0 is a valid fallback). Complexity O(n · B) with B = 31, versus O(n²) brute force. The C++ version uses an index-based node pool instead of new; it is faster and avoids leaks, and it is the standard competitive-programming layout.

Maximum XOR With an Element From Array (1707) adds a constraint: partner must be ≤ m_i. Solve it offline: sort numbers and queries by m, insert numbers up to each query's limit, then query. This sort-then-insert pattern is the same offline trick used with union-find. More bit-level techniques are in bit manipulation interview tricks.

Trie Memory Considerations (the Senior-Level Discussion)

Interviewers who ask "what are the downsides of a trie?" want a memory discussion with numbers. Here is a reasoned estimate rather than a benchmark: on a 64-bit JVM with compressed references, a Node holding a 26-element reference array costs about 16 bytes of array header plus 26 × 4 bytes of references, plus the node object itself, so on the order of 130-150 bytes per node. Insert 10⁵ words of average length 10 with little prefix sharing and you can approach 10⁶ nodes, which is over 100 MB. Most of those 26 slots are null.

Real systems use these: Linux's routing tables and many IP lookup structures are compressed tries for longest-prefix match; Lucene (which powers Elasticsearch) uses finite state transducers for its term dictionary; Redis's internal radix tree (rax) backs streams. Mentioning one of these, accurately, is a strong signal. For how search engines store terms, see the inverted index explainer.

How Tries Show Up in Interviews

Questions to ask before coding: Is the alphabet lowercase a–z only? Can words repeat? Are empty strings possible? Is memory constrained? Each changes the node design. And state complexities in terms of word length L and total characters S, not just n.

Common Trie Mistakes

• Treating leaves as word ends. "app" inside "apple" is not a leaf. Use an explicit flag.
• search returning true for prefixes because the walk succeeded but isEnd was not checked.
• Allocating 26-child arrays for Unicode or mixed-case input, causing index-out-of-bounds. Ask about the alphabet.
• Building strings during DFS in Word Search II (path + ch on every step), which adds O(L) per step. Store the word at the end node.
• Reporting duplicates in Word Search II when a word is reachable along two paths.
• Forgetting to restore the board cell after backtracking.
• XOR trie with inconsistent bit widths between insert and query, or querying an empty trie.

Trie Practice List

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.