Skip to main content

20. Implement Trie (Prefix Tree)

mediumAsked at Dropbox

Build a prefix tree that supports insert, search, and startsWith — Dropbox uses a trie variant to power instant path-autocomplete in the desktop client as you type a destination folder.

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

Problem

Implement a trie with insert, search, and startsWith methods. insert(word) inserts a word into the trie. search(word) returns true if the word is in the trie (must be a complete word). startsWith(prefix) returns true if any word in the trie starts with the given prefix.

Constraints

  • 1 <= word.length <= 2000
  • word and prefix consist of lowercase English letters only
  • At most 3 * 10^4 calls total 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 inserting 'apple', 'app' is a prefix but not a complete word. After inserting 'app', search('app') returns true.

Example 2

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

Approaches

1. Hash map per node

Each node stores a children map (character → node) and an isEnd flag. Traverse on insert and lookup, creating nodes as needed.

Time
O(m) per op, m = word length
Space
O(n*m) total
class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  insert(word) {
    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;
  }
  _traverse(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch);
    }
    return node;
  }
  search(word) {
    const node = this._traverse(word);
    return node !== null && node.isEnd;
  }
  startsWith(prefix) {
    return this._traverse(prefix) !== null;
  }
}

Tradeoff:

2. Fixed-size array per node

Replace the map with a 26-element array indexed by char code. Faster in practice for lowercase-only alphabets due to array locality.

Time
O(m) per op
Space
O(26*n*m) worst case
class TrieNode {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEnd = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      const idx = ch.charCodeAt(0) - 97;
      if (!node.children[idx]) node.children[idx] = new TrieNode();
      node = node.children[idx];
    }
    node.isEnd = true;
  }
  _traverse(str) {
    let node = this.root;
    for (const ch of str) {
      const idx = ch.charCodeAt(0) - 97;
      if (!node.children[idx]) return null;
      node = node.children[idx];
    }
    return node;
  }
  search(word) {
    const node = this._traverse(word);
    return node !== null && node.isEnd;
  }
  startsWith(prefix) {
    return this._traverse(prefix) !== null;
  }
}

Tradeoff:

Dropbox-specific tips

Dropbox interviewers connect this to the folder-path autocomplete feature. Expect a follow-up asking you to return all files under a given prefix — that requires a DFS/BFS from the terminal prefix node. Practice walking the trie recursively and collecting all words before your interview.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →