#39 · Tries

Implement Trie (Prefix Tree)

Design a Trie with insert(word), search(word) for an exact stored word, and startsWith(prefix) for any stored word that begins with the prefix.

MediumLeetCode

Current
On path / queued
Done
Cycle / blocked

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Trie (prefix tree)

A tree where each edge is one letter and each root-to-node path spells a prefix. Words that share a prefix share the nodes of that prefix. A flag on a node marks that a stored word ends there.

Memory layout

Either one object per node holding a letter-to-child table, or one big flat table with a fixed number of slots per node (26 for lowercase letters) where a child is stored as a node id. The flat form has no per-node allocation and walks contiguous memory.

Operation	Cost
insert / search / startsWith	O(L), L = length of the word or prefix
space	O(total letters) worst case; shared prefixes are stored once

Hash set of words and prefixes

Store every word and every prefix of every word as a separate string. Lookups are O(L) because hashing reads the string once.

Memory layout

Hash table of string objects; each prefix is its own copy, so a word of length L adds L strings of total size O(L²).

Operation	Cost
search / startsWith	O(L) average
insert	O(L²) time and space

Why it fits

A prefix question asks about a path from the start of the word. A trie turns the question into walking that path, one letter at a time, with no comparison against other words.
Search and startsWith are the same walk. They only differ in the last check: a word must end at the node, a prefix only needs the node to exist.
Shared prefixes are stored once, so a thousand words that start with "inter" pay for those five letters once.

Why alternatives degrade

Sorted array + binary search:: Prefix queries are fast (binary search finds the first match), but inserting into a sorted array shifts elements: O(n) per insert.
Plain list of words:: Every query scans every stored word: O(total letters) per search.
Set of all prefixes:: Queries are O(L), but inserting stores O(L²) letters because every prefix is copied.

Four approaches, from naive to production

1 · beginner

List of words, scan on every query

time insert O(1), search / startsWith O(n·L)space O(n·L)

Keep the inserted words in a list. search compares each stored word to the query; startsWith checks whether any stored word begins with the prefix.

class Trie {
    vector<string> words;
public:
    void insert(string word) {
        words.push_back(word);
    }
    bool search(string word) {
        for (const string& w : words) {
            if (w == word) return true;
        }
        return false;
    }
    bool startsWith(string prefix) {
        for (const string& w : words) {
            if (w.compare(0, prefix.size(), prefix) == 0) return true;
        }
        return false;
    }
};

class Trie {
    private List<String> words = new ArrayList<>();
    public void insert(String word) {
        words.add(word);
    }
    public boolean search(String word) {
        for (String w : words) {
            if (w.equals(word)) return true;
        }
        return false;
    }
    public boolean startsWith(String prefix) {
        for (String w : words) {
            if (w.startsWith(prefix)) return true;
        }
        return false;
    }
}

class Trie:
    def __init__(self):
        self.words = []
    def insert(self, word):
        self.words.append(word)
    def search(self, word):
        for w in self.words:
            if w == word: return True
        return False
    def starts_with(self, prefix):
        for w in self.words:
            if w.startswith(prefix): return True
        return False

class Trie {
  private words: string[] = [];

  insert(word: string): void {
    this.words.push(word);
  }

  search(word: string): boolean {
    for (const w of this.words) {
      if (w === word) return true;
    }
    return false;
  }

  startsWith(prefix: string): boolean {
    for (const w of this.words) {
      if (w.startsWith(prefix)) return true;
    }
    return false;
  }
}

Flaws & bottlenecks

Every query touches every stored word, so cost grows with the size of the dictionary.
Duplicates pile up: inserting the same word twice stores it twice.
Shared prefixes are copied over and over.

Interviewer cross-questions

When is this acceptable?

Say: When there are very few words or very few queries. A scan of a handful of strings beats building any structure. The point of the interview is to notice that the work does not depend on the query length alone.

How would you speed up search but not startsWith?

Say: A hash set of whole words makes search O(L). startsWith still needs a scan or a prefix structure, which is why people reach for a trie.

What does a query cost in terms of the letters compared?

Say: Up to the sum of the lengths of all stored words (each comparison can read both strings). A trie reads only the L letters of the query.

2 · intermediate

Two hash sets: words and prefixes

time insert O(L²), search / startsWith O(L)space O(n·L²)

On insert, add the word to a word set and add every prefix to a prefix set. search is a lookup in the word set and startsWith is a lookup in the prefix set.

class Trie {
    unordered_set<string> words;
    unordered_set<string> prefixes;
public:
    void insert(string word) {
        words.insert(word);
        for (int i = 1; i <= (int)word.size(); i++) {
            prefixes.insert(word.substr(0, i));
        }
    }
    bool search(string word) {
        return words.count(word) > 0;
    }
    bool startsWith(string prefix) {
        return prefixes.count(prefix) > 0;
    }
};

class Trie {
    private Set<String> words = new HashSet<>();
    private Set<String> prefixes = new HashSet<>();
    public void insert(String word) {
        words.add(word);
        for (int i = 1; i <= word.length(); i++) {
            prefixes.add(word.substring(0, i));
        }
    }
    public boolean search(String word) {
        return words.contains(word);
    }
    public boolean startsWith(String prefix) {
        return prefixes.contains(prefix);
    }
}

class Trie:
    def __init__(self):
        self.words = set()
        self.prefixes = set()
    def insert(self, word):
        self.words.add(word)
        for i in range(1, len(word) + 1):
            self.prefixes.add(word[:i])
    def search(self, word):
        return word in self.words
    def starts_with(self, prefix):
        return prefix in self.prefixes

class Trie {
  private words = new Set<string>();
  private prefixes = new Set<string>();

  insert(word: string): void {
    this.words.add(word);
    for (let i = 1; i <= word.length; i++) {
      this.prefixes.add(word.slice(0, i));
    }
  }

  search(word: string): boolean {
    return this.words.has(word);
  }

  startsWith(prefix: string): boolean {
    return this.prefixes.has(prefix);
  }
}

Flaws & bottlenecks

Each prefix is a separate string, so a word of length L costs about L²/2 letters of storage.
Inserting long words is slow because each slice copies its characters.
It works only for exact prefix and exact word queries; it cannot be extended to wildcards or "all words with this prefix".

Interviewer cross-questions

Why is insert O(L²)?

Say: There are L prefixes and the k-th has k letters, so building them all copies 1 + 2 + … + L letters.

Can you list all words that start with a prefix?

Say: Not with these sets. You would have to scan every word. A trie lets you walk to the prefix node and enumerate its subtree.

How is this related to a trie?

Say: A trie stores the same set of prefixes, but as shared paths instead of separate strings. Each prefix costs one node instead of a full copy.

3 · advanced

Trie with a child table per node

time O(L) per operationspace O(total letters)

Each node holds a letter-to-child table and an end-of-word flag. insert walks and creates missing children. A shared walk helper returns the node for a string, and search / startsWith differ only in the final check.

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};
class Trie {
    TrieNode* root = new TrieNode();
    TrieNode* walk(const string& s) {
        TrieNode* node = root;
        for (char ch : s) {
            auto it = node->children.find(ch);
            if (it == node->children.end()) return nullptr;
            node = it->second;
        }
        return node;
    }
public:
    void insert(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) node->children[ch] = new TrieNode();
            node = node->children[ch];
        }
        node->isEnd = true;
    }
    bool search(string word) {
        TrieNode* node = walk(word);
        return node != nullptr && node->isEnd;
    }
    bool startsWith(string prefix) {
        return walk(prefix) != nullptr;
    }
};

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}
class Trie {
    private TrieNode root = new TrieNode();
    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) node.children.put(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }
    private TrieNode walk(String s) {
        TrieNode node = root;
        for (char ch : s.toCharArray()) {
            TrieNode next = node.children.get(ch);
            if (next == null) return null;
            node = next;
        }
        return node;
    }
    public boolean search(String word) {
        TrieNode node = walk(word);
        return node != null && node.isEnd;
    }
    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }
}

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

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children: node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
    def _walk(self, s):
        node = self.root
        for ch in s:
            nxt = node.children.get(ch)
            if nxt is None: return None
            node = nxt
        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

class TrieNode {
  children = new Map<string, TrieNode>();
  isEnd = false;
}

class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch)!;
    }
    node.isEnd = true;
  }

  private walk(s: string): TrieNode | null {
    let node = this.root;
    for (const ch of s) {
      const next = node.children.get(ch);
      if (!next) return null;
      node = next;
    }
    return node;
  }

  search(word: string): boolean {
    const node = this.walk(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix: string): boolean {
    return this.walk(prefix) !== null;
  }
}

Flaws & bottlenecks

One object (and one hash table) per node: a lot of small allocations and pointer chasing.
A hash table per node costs far more memory than the letter it represents, especially for nodes with a single child.
Deleting a word is awkward: you must remove nodes bottom-up until you reach one that is shared or ends another word.

Interviewer cross-questions

Why does startsWith not check the end flag?

Say: A prefix only needs the path to exist. The flag is needed for search because "ca" being a path does not mean "ca" was inserted as a word.

How would you support delete?

Say: Walk to the end node and clear its flag. Then walk back up, removing each node that has no children and no end flag, stopping at the first node that is still needed.

What about a large alphabet, like unicode?

Say: A table of children per node keeps memory proportional to the children actually present, so it scales. A fixed array of 26 per node would be wasteful at that size.

4 · expert

Flat 26-slot table, no node objects

time O(L) per operationspace O(26 · nodes)

Store the whole trie as one flat table: node n owns slots n×26 … n×26+25, each holding a child node id (0 = none) for one letter, plus a parallel list of end flags. No per-node objects, and walking is just index arithmetic.

class Trie {
    vector<int> next = vector<int>(26, 0);
    vector<bool> end = {false};
    int find(const string& s) {
        int node = 0;
        for (char ch : s) {
            node = next[node * 26 + (ch - 'a')];
            if (node == 0) return -1;
        }
        return node;
    }
public:
    void insert(string word) {
        int node = 0;
        for (char ch : word) {
            int c = ch - 'a';
            if (next[node * 26 + c] == 0) {
                next[node * 26 + c] = end.size();
                end.push_back(false);
                next.insert(next.end(), 26, 0);
            }
            node = next[node * 26 + c];
        }
        end[node] = true;
    }
    bool search(string word) {
        int node = find(word);
        return node != -1 && end[node];
    }
    bool startsWith(string prefix) {
        return find(prefix) != -1;
    }
};

class Trie {
    private List<Integer> next = new ArrayList<>(Collections.nCopies(26, 0));
    private List<Boolean> end = new ArrayList<>(List.of(false));
    public void insert(String word) {
        int node = 0;
        for (char ch : word.toCharArray()) {
            int c = ch - 'a';
            if (next.get(node * 26 + c) == 0) {
                next.set(node * 26 + c, end.size());
                end.add(false);
                next.addAll(Collections.nCopies(26, 0));
            }
            node = next.get(node * 26 + c);
        }
        end.set(node, true);
    }
    private int find(String s) {
        int node = 0;
        for (char ch : s.toCharArray()) {
            node = next.get(node * 26 + (ch - 'a'));
            if (node == 0) return -1;
        }
        return node;
    }
    public boolean search(String word) {
        int node = find(word);
        return node != -1 && end.get(node);
    }
    public boolean startsWith(String prefix) {
        return find(prefix) != -1;
    }
}

class Trie:
    def __init__(self):
        self.next = [0] * 26
        self.end = [False]
    def insert(self, word):
        node = 0
        for ch in word:
            c = ord(ch) - 97
            if self.next[node * 26 + c] == 0:
                self.next[node * 26 + c] = len(self.end)
                self.end.append(False)
                self.next.extend([0] * 26)
            node = self.next[node * 26 + c]
        self.end[node] = True
    def _find(self, s):
        node = 0
        for ch in s:
            node = self.next[node * 26 + ord(ch) - 97]
            if node == 0: return -1
        return node
    def search(self, word):
        node = self._find(word)
        return node != -1 and self.end[node]
    def starts_with(self, prefix):
        return self._find(prefix) != -1

class Trie {
  private next: number[] = new Array(26).fill(0);
  private end: boolean[] = [false];

  insert(word: string): void {
    let node = 0;
    for (const ch of word) {
      const c = ch.charCodeAt(0) - 97;
      if (this.next[node * 26 + c] === 0) {
        this.next[node * 26 + c] = this.end.length;
        this.end.push(false);
        this.next.push(...new Array(26).fill(0));
      }
      node = this.next[node * 26 + c];
    }
    this.end[node] = true;
  }

  private find(s: string): number {
    let node = 0;
    for (const ch of s) {
      node = this.next[node * 26 + ch.charCodeAt(0) - 97];
      if (node === 0) return -1;
    }
    return node;
  }

  search(word: string): boolean {
    const node = this.find(word);
    return node !== -1 && this.end[node];
  }

  startsWith(prefix: string): boolean {
    return this.find(prefix) !== -1;
  }
}

Flaws & bottlenecks

Every node reserves 26 slots even if it has one child, so sparse tries waste memory.
It assumes lowercase letters: any other character corrupts the index (a production version would validate or map characters).
Growing the table by appending a row relies on 0 meaning "no child", so the root must never be a child.

Interviewer cross-questions

Why use a flat table instead of objects?

Say: Contiguous memory is cache friendly, there is one allocation instead of one per node, and node ids are small integers that are easy to serialize. In languages with garbage collection it also removes pressure on the collector.

Why is 0 a safe "no child" value?

Say: Node 0 is the root, and the root is never a child of anything. So 0 in a child slot can only mean "empty".

How would you pick between the table and a map per node?

Say: Dense, small alphabet and many words: the flat table wins on speed. Large alphabet or sparse branching: use a map or a sorted list of children to save memory.

Synchronized code walkthrough

Showing: List of words, scan on every query — shares the player above; click any step to jump.

class Trie {
    vector<string> words;
public:
    void insert(string word) {
        words.push_back(word);
    }
    bool search(string word) {
        for (const string& w : words) {
            if (w == word) return true;
        }
        return false;
    }
    bool startsWith(string prefix) {
        for (const string& w : words) {
            if (w.compare(0, prefix.size(), prefix) == 0) return true;
        }
        return false;
    }
};

class Trie {
    private List<String> words = new ArrayList<>();
    public void insert(String word) {
        words.add(word);
    }
    public boolean search(String word) {
        for (String w : words) {
            if (w.equals(word)) return true;
        }
        return false;
    }
    public boolean startsWith(String prefix) {
        for (String w : words) {
            if (w.startsWith(prefix)) return true;
        }
        return false;
    }
}

class Trie:
    def __init__(self):
        self.words = []
    def insert(self, word):
        self.words.append(word)
    def search(self, word):
        for w in self.words:
            if w == word: return True
        return False
    def starts_with(self, prefix):
        for w in self.words:
            if w.startswith(prefix): return True
        return False

class Trie {
  private words: string[] = [];

  insert(word: string): void {
    this.words.push(word);
  }

  search(word: string): boolean {
    for (const w of this.words) {
      if (w === word) return true;
    }
    return false;
  }

  startsWith(prefix: string): boolean {
    for (const w of this.words) {
      if (w.startsWith(prefix)) return true;
    }
    return false;
  }
}

class Trie {
    unordered_set<string> words;
    unordered_set<string> prefixes;
public:
    void insert(string word) {
        words.insert(word);
        for (int i = 1; i <= (int)word.size(); i++) {
            prefixes.insert(word.substr(0, i));
        }
    }
    bool search(string word) {
        return words.count(word) > 0;
    }
    bool startsWith(string prefix) {
        return prefixes.count(prefix) > 0;
    }
};

class Trie {
    private Set<String> words = new HashSet<>();
    private Set<String> prefixes = new HashSet<>();
    public void insert(String word) {
        words.add(word);
        for (int i = 1; i <= word.length(); i++) {
            prefixes.add(word.substring(0, i));
        }
    }
    public boolean search(String word) {
        return words.contains(word);
    }
    public boolean startsWith(String prefix) {
        return prefixes.contains(prefix);
    }
}

class Trie:
    def __init__(self):
        self.words = set()
        self.prefixes = set()
    def insert(self, word):
        self.words.add(word)
        for i in range(1, len(word) + 1):
            self.prefixes.add(word[:i])
    def search(self, word):
        return word in self.words
    def starts_with(self, prefix):
        return prefix in self.prefixes

class Trie {
  private words = new Set<string>();
  private prefixes = new Set<string>();

  insert(word: string): void {
    this.words.add(word);
    for (let i = 1; i <= word.length; i++) {
      this.prefixes.add(word.slice(0, i));
    }
  }

  search(word: string): boolean {
    return this.words.has(word);
  }

  startsWith(prefix: string): boolean {
    return this.prefixes.has(prefix);
  }
}

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};
class Trie {
    TrieNode* root = new TrieNode();
    TrieNode* walk(const string& s) {
        TrieNode* node = root;
        for (char ch : s) {
            auto it = node->children.find(ch);
            if (it == node->children.end()) return nullptr;
            node = it->second;
        }
        return node;
    }
public:
    void insert(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) node->children[ch] = new TrieNode();
            node = node->children[ch];
        }
        node->isEnd = true;
    }
    bool search(string word) {
        TrieNode* node = walk(word);
        return node != nullptr && node->isEnd;
    }
    bool startsWith(string prefix) {
        return walk(prefix) != nullptr;
    }
};

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}
class Trie {
    private TrieNode root = new TrieNode();
    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) node.children.put(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }
    private TrieNode walk(String s) {
        TrieNode node = root;
        for (char ch : s.toCharArray()) {
            TrieNode next = node.children.get(ch);
            if (next == null) return null;
            node = next;
        }
        return node;
    }
    public boolean search(String word) {
        TrieNode node = walk(word);
        return node != null && node.isEnd;
    }
    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }
}

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

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children: node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
    def _walk(self, s):
        node = self.root
        for ch in s:
            nxt = node.children.get(ch)
            if nxt is None: return None
            node = nxt
        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

class TrieNode {
  children = new Map<string, TrieNode>();
  isEnd = false;
}

class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch)!;
    }
    node.isEnd = true;
  }

  private walk(s: string): TrieNode | null {
    let node = this.root;
    for (const ch of s) {
      const next = node.children.get(ch);
      if (!next) return null;
      node = next;
    }
    return node;
  }

  search(word: string): boolean {
    const node = this.walk(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix: string): boolean {
    return this.walk(prefix) !== null;
  }
}

class Trie {
    vector<int> next = vector<int>(26, 0);
    vector<bool> end = {false};
    int find(const string& s) {
        int node = 0;
        for (char ch : s) {
            node = next[node * 26 + (ch - 'a')];
            if (node == 0) return -1;
        }
        return node;
    }
public:
    void insert(string word) {
        int node = 0;
        for (char ch : word) {
            int c = ch - 'a';
            if (next[node * 26 + c] == 0) {
                next[node * 26 + c] = end.size();
                end.push_back(false);
                next.insert(next.end(), 26, 0);
            }
            node = next[node * 26 + c];
        }
        end[node] = true;
    }
    bool search(string word) {
        int node = find(word);
        return node != -1 && end[node];
    }
    bool startsWith(string prefix) {
        return find(prefix) != -1;
    }
};

class Trie {
    private List<Integer> next = new ArrayList<>(Collections.nCopies(26, 0));
    private List<Boolean> end = new ArrayList<>(List.of(false));
    public void insert(String word) {
        int node = 0;
        for (char ch : word.toCharArray()) {
            int c = ch - 'a';
            if (next.get(node * 26 + c) == 0) {
                next.set(node * 26 + c, end.size());
                end.add(false);
                next.addAll(Collections.nCopies(26, 0));
            }
            node = next.get(node * 26 + c);
        }
        end.set(node, true);
    }
    private int find(String s) {
        int node = 0;
        for (char ch : s.toCharArray()) {
            node = next.get(node * 26 + (ch - 'a'));
            if (node == 0) return -1;
        }
        return node;
    }
    public boolean search(String word) {
        int node = find(word);
        return node != -1 && end.get(node);
    }
    public boolean startsWith(String prefix) {
        return find(prefix) != -1;
    }
}

class Trie:
    def __init__(self):
        self.next = [0] * 26
        self.end = [False]
    def insert(self, word):
        node = 0
        for ch in word:
            c = ord(ch) - 97
            if self.next[node * 26 + c] == 0:
                self.next[node * 26 + c] = len(self.end)
                self.end.append(False)
                self.next.extend([0] * 26)
            node = self.next[node * 26 + c]
        self.end[node] = True
    def _find(self, s):
        node = 0
        for ch in s:
            node = self.next[node * 26 + ord(ch) - 97]
            if node == 0: return -1
        return node
    def search(self, word):
        node = self._find(word)
        return node != -1 and self.end[node]
    def starts_with(self, prefix):
        return self._find(prefix) != -1

class Trie {
  private next: number[] = new Array(26).fill(0);
  private end: boolean[] = [false];

  insert(word: string): void {
    let node = 0;
    for (const ch of word) {
      const c = ch.charCodeAt(0) - 97;
      if (this.next[node * 26 + c] === 0) {
        this.next[node * 26 + c] = this.end.length;
        this.end.push(false);
        this.next.push(...new Array(26).fill(0));
      }
      node = this.next[node * 26 + c];
    }
    this.end[node] = true;
  }

  private find(s: string): number {
    let node = 0;
    for (const ch of s) {
      node = this.next[node * 26 + ch.charCodeAt(0) - 97];
      if (node === 0) return -1;
    }
    return node;
  }

  search(word: string): boolean {
    const node = this.find(word);
    return node !== -1 && this.end[node];
  }

  startsWith(prefix: string): boolean {
    return this.find(prefix) !== -1;
  }
}