Skip to main content

208. Implement Trie (Prefix Tree)

mediumAsked at GoDaddy

Build a trie that supports insert, search, and prefix lookup — GoDaddy's domain-search autocomplete is a direct application of this structure, making prefix-tree questions a staple in their platform-engineering interviews.

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

Problem

Implement the Trie class with three methods: insert(word) inserts word into the trie, search(word) returns true if word is in the trie, and startsWith(prefix) returns true if any word in the trie starts with the given prefix.

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters
  • At most 3 * 10^4 calls 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]

Approaches

1. Hash-map children

Each trie node holds a Map from character to child node plus an isEnd flag; no fixed 26-element array needed.

Time
O(m) per operation where m = word length
Space
O(n * m) total nodes
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;
  }
  search(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) return false;
      node = node.children.get(ch);
    }
    return node.isEnd;
  }
  startsWith(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) return false;
      node = node.children.get(ch);
    }
    return true;
  }
}

Tradeoff:

2. Array children (fixed 26)

Use a 26-element array indexed by char code for O(1) child access without hash overhead; trades flexibility for speed.

Time
O(m) per operation
Space
O(n * 26 * m) — more memory per node
class TrieNode {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEnd = false;
  }
}

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

Tradeoff:

GoDaddy-specific tips

GoDaddy's domain-autocomplete team will push you to discuss how the trie scales when the alphabet expands beyond lowercase ASCII — think punycode internationalized domain names. Mention compressed tries (Patricia/Radix) if you want to stand out on memory efficiency.

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 GoDaddy interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →