Implement Trie (Prefix Tree)
A trie (prefix tree) is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Implement the Trie class with insert, search, and startsWith methods.

30:00

Implement Trie (Prefix Tree)
medium
Topics
Companies

A trie (prefix tree) is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Implement the Trie class with insert, search, and startsWith methods.

Example 1:
Input: {"operations":["Trie","insert","search","search","startsWith","insert","search"],"args":[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]}
Output: [null,null,true,false,true,null,true]
Constraints:

  • 1≤word.length,prefix.length≤20001 \leq \text{word.length}, \text{prefix.length} \leq 2000

  • word and prefix consist only of lowercase English letters.

  • At most 3×1043 \times 10^4 calls in total to insert, search, and startsWith.

Input
arr ={"operations":["Trie","insert","search","search","startsWith","insert","search"],"args":[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]}

Initialize empty Trie

Trie StructurerootEmpty Trie
Current
In Path
Word End
Variables
VariableValue
stepinit
path
resultnull
DepthFunction Call
Stack empty
0/34