Skip to main content

208. Implement Trie (Prefix Tree)

mediumAsked at Cisco

Implement Trie at Cisco is the OOP design question they ask when the team works on prefix-match systems — IP-prefix routing tables, autocomplete in their config CLIs, or rule lookup. The interviewer is checking whether you can build the class cleanly and whether you handle the prefix-vs-full-word distinction.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Cisco loops.

  • Glassdoor (2026-Q1)— Cisco SDE-II onsite reports cite Trie as a 30-45 minute OOP design round.
  • Blind (2025-10)— Cisco interview thread lists Trie among the standard OOP design problems for backend roles.

Problem

A trie (pronounced as 'try') or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Implement the Trie class: Trie() initializes the trie object. void insert(String word) inserts the string word into the trie. boolean search(String word) returns true if the string word is in the trie (i.e., was inserted before) and false otherwise. boolean startsWith(String prefix) returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.

Examples

Example 1

Input
Trie(); insert("apple"); search("apple"); search("app"); startsWith("app"); insert("app"); search("app")
Output
[null,null,true,false,true,null,true]

Explanation: After insert apple: search 'apple' true, search 'app' false (it's a prefix, not a stored word), startsWith 'app' true.

Approaches

1. Brute-force: array of strings, linear scan

Store words in a simple array. search = exact match scan, startsWith = prefix scan.

Time
O(n * L) per op
Space
O(n * L)
class TrieBrute {
  constructor() { this.words = []; }
  insert(w) { this.words.push(w); }
  search(w) { return this.words.includes(w); }
  startsWith(p) { return this.words.some(w => w.startsWith(p)); }
}

Tradeoff: Wrong answer for the rubric — Cisco wants the trie data structure specifically. This is just a strawman to show you understand the semantics.

2. Trie with object children + isEnd flag (optimal)

Each node has a map of children (one per letter) and a boolean isEnd. Insert walks/creates nodes letter-by-letter. Search walks and checks isEnd at the terminal. startsWith walks and ignores isEnd.

Time
O(L) per op
Space
O(total characters inserted)
class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}
class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.isEnd = true;
  }
  search(word) {
    const node = this._walk(word);
    return !!node && node.isEnd;
  }
  startsWith(prefix) {
    return this._walk(prefix) !== null;
  }
  _walk(s) {
    let node = this.root;
    for (const ch of s) {
      if (!node.children[ch]) return null;
      node = node.children[ch];
    }
    return node;
  }
}

Tradeoff: Every op is O(L) where L = word/prefix length, independent of how many words are in the trie. The isEnd flag is what differentiates 'inserted' from 'is a prefix of an inserted word.' The _walk helper keeps search and startsWith from duplicating logic.

3. Fixed-size array of children (for lowercase only)

Same scaffold but children is a length-26 array indexed by `charCodeAt(c) - 97`. Avoids the object/hash overhead.

Time
O(L) per op
Space
O(26 * total nodes)
class TrieNodeArr {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEnd = false;
  }
}
class TrieArr {
  constructor() { this.root = new TrieNodeArr(); }
  _idx(ch) { return ch.charCodeAt(0) - 97; }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      const i = this._idx(ch);
      if (!node.children[i]) node.children[i] = new TrieNodeArr();
      node = node.children[i];
    }
    node.isEnd = true;
  }
  search(word) {
    const node = this._walk(word);
    return !!node && node.isEnd;
  }
  startsWith(prefix) {
    return this._walk(prefix) !== null;
  }
  _walk(s) {
    let node = this.root;
    for (const ch of s) {
      const i = this._idx(ch);
      if (!node.children[i]) return null;
      node = node.children[i];
    }
    return node;
  }
}

Tradeoff: Faster constant factor (array lookup beats object hash) but wastes 26 slots per node even if most are null. Better when the alphabet is small and you know it upfront. Cisco interviewers like seeing you raise this tradeoff.

Cisco-specific tips

Cisco interviewers want you to draw a sample trie on the whiteboard BEFORE you write code — show 'apple' and 'app' as overlapping paths with isEnd marked at different depths. State the invariant: 'isEnd = true means a word terminates here; absence of isEnd means this is only a prefix.' Then write the class. The _walk helper is what they're grading you on — duplicating the loop in search and startsWith is the lazy answer.

Common mistakes

  • Forgetting `node.isEnd = true` in insert — search becomes equivalent to startsWith.
  • Returning the wrong thing from search — must check isEnd at the terminal node, not just 'did we successfully walk.'
  • Implementing search and startsWith as duplicate code instead of factoring out a `_walk` helper.

Follow-up questions

An interviewer at Cisco may pivot to one of these next:

  • Add and Search Word - Data structure design (LC 211) — same trie but search supports '.' wildcards.
  • Word Search II (LC 212) — trie + DFS on a grid; classic Cisco follow-up.
  • Longest Common Prefix of an array (LC 14) — insert all, walk while single child.
  • Implement Magic Dictionary (LC 676) — trie + 'exactly one letter differs' search.
  • Implement delete — must clean up empty subtrees to avoid leaks.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Object children or array-of-26?

Object children is more memory-efficient when the alphabet is unknown or large; array-of-26 is faster per op for lowercase English. Cisco interviewers respect candidates who raise the tradeoff. For the LeetCode constraints (lowercase only, 30k ops), either is fast enough.

Why is the isEnd flag necessary?

Because without it you can't tell whether you've inserted 'app' specifically or only 'apple' (which also creates an 'app' path). The flag is the one bit per node that distinguishes 'a stored word ends here' from 'this is only an internal path.'

What's the production version?

Cisco's actual prefix-routing code uses a compressed trie (Patricia trie / radix tree) where chains of single-child nodes are collapsed into one edge with a string label. Same Big-O but much less memory. Mention this as the 'in production' answer and Cisco interviewers light up.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Implement Trie (Prefix Tree) and other Cisco interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →