Implement Trie (Prefix Tree)

MediumTrie Design String Hash Table

A search box suggests completions while the user types. Behind it sits a trie (prefix tree): a tree of letters in which every stored word is a path from the root, so whole words and prefixes can be checked in time proportional to their length.

Implement the Trie class:

Trie() creates an empty trie.
insert(word) stores word; storing a word that is already present changes nothing.
search(word) returns true only if word itself was stored as a complete word.
startsWith(prefix) returns true if at least one stored word begins with prefix; every word counts as a prefix of itself.

The tests call the methods one after another.

Example 1

Input: ["Trie","insert","insert","startsWith","search","search","startsWith"]
[[],["sea"],["seal"],["se"],["sea"],["seas"],["seat"]]
Output: [null,null,null,true,true,false,false]

Explanation: Both stored words begin with "se", and "sea" was stored as a word. "seas" was never stored, and no stored word begins with "seat".

Example 2

Input: ["Trie","search","insert","search","startsWith","search"]
[[],["map"],["maple"],["map"],["map"],["maple"]]
Output: [null,false,null,false,true,true]

Explanation: Nothing is found before the first insert. After storing "maple", "map" is only a prefix: startsWith finds it but search does not.

Constraints

Every word and prefix is between 1 and 2000 characters long.
Words and prefixes use only lowercase English letters.
A test makes at most 30,000 calls in total.

💡 Hint 1

Each node represents a prefix, and each edge adds one letter. The root is the empty prefix.

💡 Hint 2

Give each node up to 26 children (an array or a map) and a flag saying whether a word ends exactly here.

💡 Hint 3

search and startsWith walk the same path; they only differ in whether the final node must carry the end-of-word flag.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Each trie node holds its children (keyed by letter) and an end flag. insert walks from the root letter by letter, creating missing children, and sets end on the last node. Both queries share a helper that follows the path for a string and returns the node it reaches, or null if some letter is missing. startsWith only needs that node to exist; search additionally requires its end flag, which is what separates a stored word from a mere prefix.

Time O(L) per call, where L is the length of the word or prefixSpace O(total letters inserted)

class Trie {
  constructor() {
    this.root = { children: new Map(), end: false };
  }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, { children: new Map(), end: false });
      node = node.children.get(ch);
    }
    node.end = true;
  }

  search(word) {
    const node = this.find(word);
    return node !== null && node.end;
  }

  startsWith(prefix) {
    return this.find(prefix) !== null;
  }

  find(s) {
    let node = this.root;
    for (const ch of s) {
      node = node.children.get(ch);
      if (!node) return null;
    }
    return node;
  }
}

class Trie {
    private static class Node {
        final Node[] next = new Node[26];
        boolean end;
    }

    private final Node root = new Node();

    public Trie() {}

    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int c = word.charAt(i) - 'a';
            if (node.next[c] == null) node.next[c] = new Node();
            node = node.next[c];
        }
        node.end = true;
    }

    public boolean search(String word) {
        Node node = find(word);
        return node != null && node.end;
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }

    private Node find(String s) {
        Node node = root;
        for (int i = 0; i < s.length() && node != null; i++) node = node.next[s.charAt(i) - 'a'];
        return node;
    }
}

class Trie {
  constructor() {

  }

  /** @param {string} word */
  insert(word) {

  }

  /**
   * @param {string} word
   * @return {boolean}
   */
  search(word) {

  }

  /**
   * @param {string} prefix
   * @return {boolean}
   */
  startsWith(prefix) {

  }
}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit