Skip to main content

19. Implement Trie (Prefix Tree)

mediumAsked at DigitalOcean

Build a prefix tree with insert, search, and startsWith operations — a data structure that powers hostname/IP prefix lookup in networking.

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

Problem

Implement a Trie with insert(word), search(word) returning true if the exact word exists, and startsWith(prefix) returning true if any inserted word starts with the prefix.

Constraints

  • 1 <= word.length <= 2000
  • word and prefix consist only of lowercase letters
  • At most 3*10^4 calls

Examples

Example 1

Input
insert('apple'); search('apple'); search('app'); startsWith('app'); insert('app'); search('app')
Output
true, false, true, true

Example 2

Input
insert('ab'); search('a')
Output
false

Approaches

1. HashMap-of-maps (flat dict)

Store the entire trie as a nested JavaScript object — correct but untyped and harder to extend.

Time
O(L) per op
Space
O(total chars)
class Trie {
  constructor(){this.root={};}
  insert(word){
    let n=this.root;
    for(const c of word){if(!n[c])n[c]={};n=n[c];}
    n.$=true;
  }
  search(word){
    let n=this.root;
    for(const c of word){if(!n[c])return false;n=n[c];}
    return !!n.$;
  }
  startsWith(prefix){
    let n=this.root;
    for(const c of prefix){if(!n[c])return false;n=n[c];}
    return true;
  }
}

Tradeoff:

2. TrieNode class with children array

Each node holds a fixed-size array of 26 children and an isEnd flag. Array indexing by char code gives cache-friendly O(1) child lookup.

Time
O(L) per op
Space
O(26 * total chars)
class TrieNode {
  constructor(){this.children=new Array(26).fill(null);this.isEnd=false;}
}
class Trie {
  constructor(){this.root=new TrieNode();}
  _idx(c){return c.charCodeAt(0)-97;}
  insert(word){
    let n=this.root;
    for(const c of word){
      const i=this._idx(c);
      if(!n.children[i])n.children[i]=new TrieNode();
      n=n.children[i];
    }
    n.isEnd=true;
  }
  search(word){
    let n=this.root;
    for(const c of word){n=n.children[this._idx(c)];if(!n)return false;}
    return n.isEnd;
  }
  startsWith(prefix){
    let n=this.root;
    for(const c of prefix){n=n.children[this._idx(c)];if(!n)return false;}
    return true;
  }
}

Tradeoff:

DigitalOcean-specific tips

DigitalOcean expects you to connect Trie to real infrastructure problems like IP routing prefix matching (CIDR lookup) or DNS wildcard resolution.

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

Practice these live with InterviewChamp.AI →