Trie Data Structure Medium 0 attempts
GeeksforGeeks ↗

Trie Data Structure

Medium Tries GeeksforGeeks

Build a trie — also called a prefix tree, a tree structure that stores strings by sharing common prefixes along shared paths — supporting three operations: insert to add a word, search to check whether an exact word has been inserted, and startsWith to check whether any inserted word begins with a given prefix.

Input Format
Implement the class Trie. Fixtures contain constructor arguments and a list of [method, ...arguments] calls. Each fixture starts with a fresh instance.
Output Format
Return the specified result from each method. The displayed output lists results in call order; undefined results appear as null.

Sample Input and Output

Example 1 · Run Sample

Input
constructorArgs = []
operations = [["insert","apple"],["search","apple"],["search","app"],["startsWith","app"],["insert","app"],["search","app"]]
Output
[null,true,false,true,null,true]

Example 2

Input
constructorArgs = []
operations = [["search","x"],["startsWith","x"],["insert","x"],["search","x"]]
Output
[false,false,null,true]
Constraints
  • 1 <= word.length <= 2000
  • word consists of lowercase English letters
  • At most 3 * 10^4 calls
Test Cases (2)
Case 1
Args: [[],[["insert","apple"],["search","apple"],["search","app"],["startsWith","app"],["insert","app"],["search","app"]]] Expected: [null,true,false,true,null,true]
Case 2
Args: [[],[["search","x"],["startsWith","x"],["insert","x"],["search","x"]]] Expected: [false,false,null,true]
Topics
Tries

Trie with Object Nodes

javascript
class Trie {
  constructor() { this.root = {}; }
  insert(word) {
    let node = this.root;
    for (const c of word) { if (!node[c]) node[c] = {}; node = node[c]; }
    node.$ = true;
  }
  search(word) {
    let node = this.root;
    for (const c of word) { if (!node[c]) return false; node = node[c]; }
    return !!node.$;
  }
  startsWith(prefix) {
    let node = this.root;
    for (const c of prefix) { if (!node[c]) return false; node = node[c]; }
    return true;
  }
}

Time: O(L) per operation | Space: O(total characters)

Saved in this browser only. Private to you.

JavaScript