# Implement Trie (Prefix Tree)
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/implement-trie-prefix-tree)
Canonical: https://scaleengineer.com/dsa/problems/implement-trie-(prefix-tree)
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Hash Table, String, Trie
**Companies:** [Docusign](https://scaleengineer.com/companies/docusign), [DoorDash](https://scaleengineer.com/companies/doordash), [Nvidia](https://scaleengineer.com/companies/nvidia), [Roblox](https://scaleengineer.com/companies/roblox), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Snowflake](https://scaleengineer.com/companies/snowflake), [Lyft](https://scaleengineer.com/companies/lyft), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Citadel](https://scaleengineer.com/companies/citadel), [X](https://scaleengineer.com/companies/x), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Pinterest](https://scaleengineer.com/companies/pinterest), [Grammarly](https://scaleengineer.com/companies/grammarly), [Block](https://scaleengineer.com/companies/block), [Mapbox](https://scaleengineer.com/companies/mapbox), [instabase](https://scaleengineer.com/companies/instabase)
---
## Problem
A [**trie**](https://en.wikipedia.org/wiki/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
## Array-based Approach
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.
**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.
**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
### Explanation
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:

```java
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;
    }
}
```
### 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

## HashMap-based Approach
This approach uses a HashMap instead of an array to store children in each node. This makes the implementation more flexible and potentially more space-efficient for sparse tries.
**Time:** O(m) for all operations, where m is the length of the word/prefix. HashMap operations are O(1) on average. · **Space:** O(N * M) where N is the number of words and M is average word length. Space is proportional to actual characters stored.
**Pros:** More space-efficient for sparse tries; Flexible for different character sets; Dynamic memory allocation based on actual usage
**Cons:** Slightly slower than array-based approach due to HashMap operations; More memory overhead per node due to HashMap structure; Hash collisions could affect performance in extreme cases
### Explanation
In this approach, we use a HashMap to store child nodes, which allows for more flexible character sets and better space efficiency when the trie is sparse.

```java
class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;
    
    public TrieNode() {
        children = new HashMap<>();
        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()) {
            current.children.putIfAbsent(ch, new TrieNode());
            current = current.children.get(ch);
        }
        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()) {
            if(!current.children.containsKey(ch)) {
                return null;
            }
            current = current.children.get(ch);
        }
        return current;
    }
}
```
### Algorithm
1. Create a TrieNode class with a HashMap for children and a boolean flag
2. For insert:
   - Start from root
   - For each character, create a new node if it doesn't exist in the HashMap
   - Mark the last node as end of word
3. For search:
   - Traverse the trie using HashMap lookups
   - 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

# Solutions
### CSharp

```csharp
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); */
```

### Java

```java
public class Implement_Trie_Prefix_Tree { public static void main ( String [] args ) { Implement_Trie_Prefix_Tree out = new Implement_Trie_Prefix_Tree (); Trie trie = out . new Trie (); trie . insert ( "abc" ); trie . insert ( "ab" ); System . out . println ( trie . search ( "ab" )); trie . insert ( "ab" ); System . out . println ( trie . search ( "ab" )); System . out . println ( trie . startsWith ( "a" )); } class TrieNode { // R children to node children private TrieNode [] children ; private final int R = 26 ; private boolean isEnd ; public TrieNode () { children = new TrieNode [ R ]; } public boolean containsKey ( char ch ) { return children [ ch - 'a' ] != null ; } public TrieNode get ( char ch ) { return children [ ch - 'a' ]; } public void put ( char ch , TrieNode node ) { children [ ch - 'a' ] = node ; } public void setEnd () { isEnd = true ; } public boolean isEnd () { return isEnd ; } } class Trie { private TrieNode root ; public Trie () { root = new TrieNode (); } // Inserts a word into the trie. public void insert ( String word ) { TrieNode node = root ; // @note:@memorize: iteration is better than recursion during trie building for ( int i = 0 ; i < word . length (); i ++) { char currentChar = word . charAt ( i ); if (! node . containsKey ( currentChar )) { node . put ( currentChar , new TrieNode ()); } node = node . get ( currentChar ); } node . setEnd (); } // search a prefix or whole key in trie and // returns the node where search ends private TrieNode searchPrefix ( String word ) { TrieNode node = root ; for ( int i = 0 ; i < word . length (); i ++) { char curLetter = word . charAt ( i ); if ( node . containsKey ( curLetter )) { node = node . get ( curLetter ); } else { return null ; } } return node ; } // Returns if the word is in the trie. public boolean search ( String word ) { TrieNode node = searchPrefix ( word ); return node != null && node . isEnd (); } // Returns if there is any word in the trie // that starts with the given prefix. public boolean startsWith ( String prefix ) { TrieNode node = searchPrefix ( prefix ); return node != null ; } } // Your Trie object will be instantiated and called as such: // Trie trie = new Trie(); // trie.insert("somestring"); // trie.search("key"); } ////// class Trie { private Trie [] children ; private boolean isEnd ; public Trie () { children = new Trie [ 26 ]; } public void insert ( String word ) { Trie node = this ; for ( char c : word . toCharArray ()) { int idx = c - 'a' ; if ( node . children [ idx ] == null ) { node . children [ idx ] = new Trie (); } node = node . children [ idx ]; } node . isEnd = true ; } public boolean search ( String word ) { Trie node = searchPrefix ( word ); return node != null && node . isEnd ; } public boolean startsWith ( String prefix ) { Trie node = searchPrefix ( prefix ); return node != null ; } private Trie searchPrefix ( String s ) { Trie node = this ; for ( char c : s . toCharArray ()) { int 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); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */
```

### JavaScript

```javascript
/** * Initialize your data structure here. */ var Trie = function () { this . children = {}; }; /** * Inserts a word into the trie. * @param {string} word * @return {void} */ Trie . prototype . insert = function ( word ) { let node = this . children ; for ( let char of word ) { if ( ! node [ char ]) { node [ char ] = {}; } node = node [ char ]; } node . isEnd = true ; }; /** * Returns if the word is in the trie. * @param {string} word * @return {boolean} */ Trie . prototype . search = function ( word ) { let node = this . searchPrefix ( word ); return node != undefined && node . isEnd != undefined ; }; Trie . prototype . searchPrefix = function ( prefix ) { let node = this . children ; for ( let char of prefix ) { if ( ! node [ char ]) return false ; node = node [ char ]; } return node ; }; /** * Returns if there is any word in the trie that starts with the given prefix. * @param {string} prefix * @return {boolean} */ Trie . prototype . startsWith = function ( prefix ) { return this . searchPrefix ( prefix ); }; /** * Your Trie object will be instantiated and called as such: * var obj = new Trie() * obj.insert(word) * var param_2 = obj.search(word) * var param_3 = obj.startsWith(prefix) */
```

### Python

```python
import collections class TrieNode : def __init__ ( self ): ''' Usually, a Python dictionary throws a KeyError if you try to get an item with a key that is not currently in the dictionary. The defaultdict in contrast will simply create any items that you try to access https://stackoverflow.com/questions/5900578/how-does-collections-defaultdict-work ''' self . child = collections . defaultdict ( TrieNode ) self . is_word = False class Trie : def __init__ ( self ): self . root = TrieNode () def insert ( self , word : str ) -> None : cur = self . root for letter in word : cur = cur . child [ letter ] cur . is_word = True def search ( self , word : str ) -> bool : cur = self . root for letter in word : # cur = cur.child[letter] ==> will not work, it will creat a default node for this letter cur = cur . child . get ( letter ) if not cur : return False return cur . is_word def startsWith ( self , prefix : str ) -> bool : cur = self . root for letter in prefix : # cur = cur.child[letter] ==> will not work, it will creat a default node for this letter cur = cur . child . get ( letter ) if not cur : return False return True # Your Trie object will be instantiated and called as such: # obj = Trie() # obj.insert(word) # param_2 = obj.search(word) # param_3 = obj.startsWith(prefix) ############ class Trie : def __init__ ( self ): self . children = [ None ] * 26 self . is_end = False def insert ( self , word : str ) -> None : node = self for c in word : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] node . is_end = True def search ( self , word : str ) -> bool : node = self . _search_prefix ( word ) return node is not None and node . is_end def startsWith ( self , prefix : str ) -> bool : node = self . _search_prefix ( prefix ) return node is not None def _search_prefix ( self , prefix : str ): node = self for c in prefix : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : return None node = node . children [ idx ] return node # Your Trie object will be instantiated and called as such: # obj = Trie() # obj.insert(word) # param_2 = obj.search(word) # param_3 = obj.startsWith(prefix) # below is using reduce() class Trie ( object ): def __init__ ( self ): T = lambda : collections . defaultdict ( T ) self . root = T () def insert ( self , word ): reduce ( dict . __getitem__ , word , self . root )[ '#' ] = True def search ( self , word ): return '#' in reduce ( lambda cur , c : cur . get ( c , {}), word , self . root ) def startsWith ( self , prefix ): return bool ( reduce ( lambda cur , c : cur . get ( c , {}), prefix , self . root ))
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/implement-trie-prefix-tree/ // Time: O(W) for insert/search/startsWith // Space: O(1) extra space for all struct TrieNode { TrieNode * next [ 26 ] = {}; bool word = false ; }; class Trie { TrieNode root ; TrieNode * find ( string & word ) { auto node = & root ; for ( char c : word ) { if ( ! node -> next [ c - 'a' ]) return NULL ; node = node -> next [ c - 'a' ]; } return node ; } public: void insert ( string word ) { auto node = & root ; for ( char c : word ) { if ( ! node -> next [ c - 'a' ]) node -> next [ c - 'a' ] = new TrieNode (); node = node -> next [ c - 'a' ]; } node -> word = true ; } bool search ( string word ) { auto node = find ( word ); return node && node -> word ; } bool startsWith ( string prefix ) { return find ( prefix ); } };
```