# Implement Trie (Prefix Tree) | LeetCode | InterviewBit | Solution Explained

LeetCode problem 208. Implement Trie (Prefix Tree) asks us to implement a Prefix Tree or a Trie. They are popularly used in the case of auto-completion. They can suggest what the next character(s) of a given prefix could be. In this writeup, I explain how we can use & implement Prefix Trees. Problem Link.

Only by typing in `lee` my browser predicted what all I could want to search. Let’s see how to implement it.

Contents

## Logic Summary

Each prefix tree consists of Nodes. In my implementation, I have:

```class Node:
def __init__(self, c, end=False):
self.c = c # current character
self.child = {} # 'x': Node()
self.end = end # is this character the last or not```

Note how close `search` and `startsWith` are in their logic. The only line changes is the last return line.

```class Trie:
def __init__(self):
self.root = Node('#')

def insert(self, word: str) -> None:
self.curr = self.root
for c in word:
if c not in self.curr.child:
self.curr.child[c] = Node(c)
self.curr = self.curr.child[c]
self.curr.end = True

def search(self, word: str) -> bool:
self.curr = self.root
for c in word:
if c in self.curr.child:
self.curr = self.curr.child[c]
else:
return False

return self.curr.end

def startsWith(self, prefix: str) -> bool:
self.curr = self.root
for c in prefix:
if c in self.curr.child:
self.curr = self.curr.child[c]
else:
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)```
##### Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

##### Assign Mice to Holes | InterviewBit | Solution Explained

June 13, 2022