Implement Trie (Prefix Tree)

Medium
2047.

Implement Trie (Prefix Tree)

Implement Trie (Prefix Tree) is a medium coding problem on strings, hash table and trie, asked in Amazon, Google and Microsoft interviews.

A trie (prefix tree) stores a set of strings so that both whole words and prefixes can be looked up quickly — the structure behind autocomplete and spell checkers. Write the class Trie:

  • Trie() creates an empty trie.
  • void insert(String word) adds word to the trie.
  • boolean search(String word) returns true if word was inserted before (as a whole word), false otherwise.
  • boolean startsWith(String prefix) returns true if some inserted word begins with prefix, false otherwise.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input
["Trie","insert","search","search","startsWith","insert","search"] [[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
Output
[null,null,true,false,true,null,true]
Explanation
"app" is a prefix of "apple" but was not inserted as a word, so `search("app")` is false until it is inserted.

Example 2

Input
["Trie","startsWith","insert","insert","startsWith","search","startsWith"] [[],["c"],["cat"],["car"],["ca"],["ca"],["cart"]]
Output
[null,false,null,null,true,false,false]
Explanation
Nothing starts with "c" in an empty trie. After "cat" and "car", "ca" is a prefix but not a word, and no word starts with "cart".

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters
  • At most 3 * 10^4 calls are made to insert, search and startsWith
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 */
var Trie = function() {
    
};

/**
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    
};

/**
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    
};

/**
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    
};

Sign in to run your own test cases

Sign in

Implement Trie (Prefix Tree) — Problem & Solution

Implement Trie (Prefix Tree) solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Implement Trie (Prefix Tree) is a medium coding problem on strings, hash table and trie, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Strings, Hash Table, Trie
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A trie (prefix tree) stores a set of strings so that both whole words and prefixes can be looked up quickly — the structure behind autocomplete and spell checkers. Write the class Trie:

  • Trie() creates an empty trie.
  • void insert(String word) adds word to the trie.
  • boolean search(String word) returns true if word was inserted before (as a whole word), false otherwise.
  • boolean startsWith(String prefix) returns true if some inserted word begins with prefix, false otherwise.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input: ["Trie","insert","search","search","startsWith","insert","search"]
[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
Output: [null,null,true,false,true,null,true]
Explanation: "app" is a prefix of "apple" but was not inserted as a word, so `search("app")` is false until it is inserted.

Example 2

Input: ["Trie","startsWith","insert","insert","startsWith","search","startsWith"]
[[],["c"],["cat"],["car"],["ca"],["ca"],["cart"]]
Output: [null,false,null,null,true,false,false]
Explanation: Nothing starts with "c" in an empty trie. After "cat" and "car", "ca" is a prefix but not a word, and no word starts with "cart".

Constraints

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

Hints for Implement Trie (Prefix Tree)

  1. Hint 1

    Words that share a beginning can share the storage for it: make a tree where each edge is a letter.

  2. Hint 2

    Each node has up to 26 children, one per letter, and a flag saying whether some word ends exactly at this node.

  3. Hint 3

    Insert walks down from the root, creating missing children. Search and startsWith walk the same path; search additionally needs the end flag on the last node, startsWith only needs the path to exist.

How to solve Implement Trie (Prefix Tree)

Each node of the trie stands for one prefix: the path of letters from the root to it. A node keeps one child per next letter and a flag marking that a whole inserted word ends there.

Approach

  1. insert(word): start at the root; for each letter, move to that child, creating it if missing. Mark the last node as a word end.
  2. Walking a string: start at the root and follow each letter's child; if one is missing, the string is not a prefix of any word.
  3. search(word): walk word; return whether the walk succeeded and the final node is marked as a word end.
  4. startsWith(prefix): return whether the walk of prefix succeeded.

Why it works

A node exists exactly when its prefix is a prefix of some inserted word, because inserting creates the whole path of a word and nothing else creates nodes. The end flag separates "was inserted" from "is only a prefix" — app and apple share every node of app, and only the flag tells them apart.

Complexity

  • Time — O(L) per operation, L = length of the argument
  • Space — O(total letters inserted × alphabet size) for array children

Pitfalls

  • Without the end flag, search("app") would wrongly succeed after inserting only apple.
  • Inserting the same word twice must not create a second path — following existing children takes care of it.

Reference solution

Python

class Trie:

    def __init__(self):
        self.root = {}  # letter -> child node; "$" marks a word end

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True

    def _walk(self, s: str):
        node = self.root
        for ch in s:
            node = node.get(ch)
            if node is None:
                return None
        return node

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and "$" in node

    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

Java

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

    private 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;
    }

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

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

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

C++

class Trie {
    struct Node {
        Node* next[26] = {};
        bool end = false;
    };
    Node* root = new Node();

    Node* walk(const string& s) {
        Node* node = root;
        for (size_t i = 0; i < s.size() && node; i++) node = node->next[s[i] - 'a'];
        return node;
    }
public:
    Trie() {}

    void insert(string word) {
        Node* node = root;
        for (char ch : word) {
            int c = ch - 'a';
            if (!node->next[c]) node->next[c] = new Node();
            node = node->next[c];
        }
        node->end = true;
    }

    bool search(string word) {
        Node* node = walk(word);
        return node && node->end;
    }

    bool startsWith(string prefix) {
        return walk(prefix) != nullptr;
    }
};

JavaScript

var Trie = function() {
    this.root = { children: {}, end: false };
};

Trie.prototype.insert = function(word) {
    var node = this.root;
    for (var i = 0; i < word.length; i++) {
        var ch = word[i];
        if (!node.children[ch]) node.children[ch] = { children: {}, end: false };
        node = node.children[ch];
    }
    node.end = true;
};

Trie.prototype.walk = function(s) {
    var node = this.root;
    for (var i = 0; i < s.length && node; i++) node = node.children[s[i]];
    return node || null;
};

Trie.prototype.search = function(word) {
    var node = this.walk(word);
    return node !== null && node.end;
};

Trie.prototype.startsWith = function(prefix) {
    return this.walk(prefix) !== null;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets