Scale Engineer

Implement Trie (Prefix Tree)

Med
#0196Time: O(m) for all operations, where m is the length of the word/prefixSpace: O(N * 26 * M) where N is the number of words and M is average word length. Each node contains an array of size 26.17 companies
Patterns
Design
Data structures
Hash TableStringTrie
Companies
DocusignDoorDashNvidiaRoblox

Prompt

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

  • Trie() Initializes the trie object.
  • void insert(String word) Inserts the string word into the trie.
  • boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
  • boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

 

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
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

 

Constraints:

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most 3 * 104 calls in total will be made to insert, search, and startsWith.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a simple array to store characters and implements a basic trie structure. Each node in the trie contains a boolean flag to mark the end of a word and an array of size 26 (for lowercase English letters) to store child nodes.

Algorithm

  1. Create a TrieNode class with an array of size 26 for children and a boolean flag
  2. For insert:
    • Start from root
    • For each character, create a new node if it doesn't exist
    • Mark the last node as end of word
  3. For search:
    • Traverse the trie following the characters
    • Return true if last node exists and is marked as end of word
  4. For startsWith:
    • Similar to search but only check if path exists

Walkthrough

In this approach, we create a TrieNode class that contains:

  1. A boolean flag isEndOfWord to mark if the node represents the end of a word
  2. An array of TrieNode references of size 26 for each possible lowercase letter

Here's the implementation:

class TrieNode {    TrieNode[] children;    boolean isEndOfWord;        public TrieNode() {        children = new TrieNode[26];        isEndOfWord = false;    }} class Trie {    private TrieNode root;        public Trie() {        root = new TrieNode();    }        public void insert(String word) {        TrieNode current = root;        for(char ch : word.toCharArray()) {            int index = ch - 'a';            if(current.children[index] == null) {                current.children[index] = new TrieNode();            }            current = current.children[index];        }        current.isEndOfWord = true;    }        public boolean search(String word) {        TrieNode node = searchNode(word);        return node != null && node.isEndOfWord;    }        public boolean startsWith(String prefix) {        return searchNode(prefix) != null;    }        private TrieNode searchNode(String str) {        TrieNode current = root;        for(char ch : str.toCharArray()) {            int index = ch - 'a';            if(current.children[index] == null) {                return null;            }            current = current.children[index];        }        return current;    }}

Complexity

Time

O(m) for all operations, where m is the length of the word/prefix

Space

O(N * 26 * M) where N is the number of words and M is average word length. Each node contains an array of size 26.

Trade-offs

Pros

  • Simple implementation with array indexing

  • Constant time lookup for children (array access)

  • Memory efficient for small alphabets

Cons

  • Fixed size array wastes space for sparse nodes

  • Not flexible for different character sets

  • Memory intensive for large character sets

Solutions

public class Trie { bool isEnd ; Trie [] children = new Trie [ 26 ]; public Trie () { } public void Insert ( string word ) { Trie node = this ; foreach ( var c in word ) { var idx = c - 'a' ; node . children [ idx ] ??= new Trie (); node = node . children [ idx ]; } node . isEnd = true ; } public bool Search ( string word ) { Trie node = SearchPrefix ( word ); return node != null && node . isEnd ; } public bool StartsWith ( string prefix ) { Trie node = SearchPrefix ( prefix ); return node != null ; } private Trie SearchPrefix ( string s ) { Trie node = this ; foreach ( var c in s ) { var idx = c - 'a' ; if ( node . children [ idx ] == null ) { return null ; } node = node . children [ idx ]; } return node ; } } /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.Insert(word); * bool param_2 = obj.Search(word); * bool param_3 = obj.StartsWith(prefix); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem