You need to login before you can make any post submission.

Add New Chapter
## Tutorial

# Trie

###### What is Trie?

###### Why trie ?

**Implementation of Trie**

**Complexity:**

### Some Standard Trie Problems

#### 1. Longest Prefix Matching

**Problem:**

**Solution:**

#### 2. Printing unique rows in a given boolean matrix

**Problem:**

**Solution:**

#### 3. Implement Reverse DNS Lookup Cache

**Problem:**

**Solution:**

#### 4. Implement Forward DNS Lookup Cache

**Problem:**

**Solution:**

- First described by
**René de la Briandais**in**1959**. - Trie is an efficient information re
val data structure.*Trie* - Also called
**digital tree**,**radix tree**or**prefix tree**, is a kind of search tree.

- Using Trie, search complexities can be brought to optimal limit (key length).
- If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree.
- Using Trie, we can search the key in
**O(M)**time. - However the penalty is on Trie storage requirements.

```
class Trie:
def __init__(self, char):
self.char = char
self.children = []
self.word_finished = False
# How many times this character appeared in the addition process
self.counter = 1
def add_word(self, word):
# Start checking from root(*) by initializing the current_node as root.
current_node = self
# We need to put every character of the word in trie.
for char in word:
# Check if the current character is there in children of the current node.
found_in_children = False
for child_node in current_node.children:
# If the current character is there in children of the current node,
# increase count and set the child_node as current node
if(child_node.char == char):
child_node.counter += 1
# Sort the children on the basis of count, such that words
# with greater frequency are suggested first.
current_node.children.sort(key = lambda x: x.counter, reverse=True)
current_node = child_node
found_in_children = True
break
# If the current character is NOT there in children of the current node,
# create a new_child_node, add this to the children of the current node
# and set this node as the current.
if (not found_in_children):
new_child_node = Trie(char)
current_node.children.append(new_child_node)
current_node = new_child_node
# If all the characters of the words are done, mark it as finished word.
current_node.word_finished = True
def search_word(self, word):
current_node = self
for char in word:
found_in_children = False
for child_node in current_node.children:
if(child_node.char == char):
current_node = child_node
found_in_children = True
break
if (not found_in_children and word != "*"):
print("Word = {} : NOT Found. Spelling Mistake".format(word))
break
if(found_in_children):
print("Word = {} : Found {} times.".format(word, current_node.counter))
return (found_in_children, current_node)
def word_suggest(self, word):
found, node = self.search_word(word)
if(found or word == "*"):
if(word == "*"):
word = ""
suggestions = self.word_suggest_util(node, word, [])
print("Suggestions are:")
for w in suggestions:
print(w, end=" ")
print("\n")
def word_suggest_util(self, node, word, word_list):
if node.word_finished:
word_list.append(word)
for child_node in node.children:
self.word_suggest_util(child_node, word+child_node.char, word_list)
return word_list
trie = Trie("*")
trie.add_word("hackathon")
trie.add_word("hack")
trie.add_word("ham")
trie.add_word("hamilton")
trie.add_word("hammer")
trie.word_suggest("hac")
trie.word_suggest("hack")
trie.word_suggest("hackathon")
trie.word_suggest("ha")
trie.word_suggest("hammer")
trie.search_word("hamlet")
```

**Output:**

**Time: O(m) :**Number of characters in the word coz the for loop is only for 26 characters and can be treated as O(1)**Auxilliary Space: O(n*m) :**At max n nodes of m length

Given a dictionary of words and an input string, find the longest prefix of the string which is also a word in dictionary.

Example:Dictionary of words : {are, area, base, cat, cater, children, basement}

Input:catererOutput:cater

Input:basemexyOutput:base

Input:childOutput:

- Build a Trie of all dictionary words.
- Once the Trie is built, traverse through it using characters of input string.
- If prefix matches a dictionary word, store current length and look for a longer match.
- Finally, return the longest match.

Given a binary matrix, print all unique rows of the given matrix.

Example:

Input:Output:{0, 1, 0, 0, 1} 0 1 0 0 1

{1, 0, 1, 1, 0} 1 0 1 1 0

{0, 1, 0, 0, 1} 1 1 1 0 0

{1, 1, 1, 0, 0}

- Consider every row as a string and add it to trie.
- Then suggest all words in trie using
**trie.word_suggest(“*“)**.

**Note:** Better solution is to use every row as a string and key to the hash or dictionary.

Reverse DNS look up is using an internet IP address to find a domain name. For example, .

Example:

Input:74.125.200.106Output:google.in

**One solution is to use Hashing.**- Advantage of Trie based solutions is, worst case upper bound is O(1) for Trie, for hashing, the best possible average case time complexity is O(1).
- Also, with Trie we can implement prefix search (finding all urls for a common prefix of IP addresses).
- The general disadvantage of Trie is large amount of memory requirement, this is not a major problem here as the alphabet size is only 11 here.
- Ten characters are needed for digits from ‘0’ to ‘9’ and one for dot (‘.’).
- The idea is to store IP addresses in Trie nodes and in the last node we store the corresponding domain name.

Forward DNS look up is getting IP address for a given domain name typed in the web browser.

**One solution is to use Hashing.**- We can implement this similar to Backward DNS Look Up but here instead of 11 we will have 27 characters (a-z & “.”).