Trie is an efficient information retrieval data structure. Use this data structure to store Strings and search strings. Your task is to use TRIE data structure and search the given string A. If found print 1 else 0.
Example 1:
Input:
N = 8
key[] = {the,a,there,answer,any,by,
         bye,their}
search = the
Output: 1
Explanation: the is present in the given
string "the a there answer any by bye
their"
Example 2:
Input:
N = 8
key[] = {the,a,there,answer,any,by,
         bye,their}
search = geeks
Output: 0
Explanation: geeks is not present in the
given string "the a there answer any by
bye their"
Your Task:
Complete insert and search function and return true if key is present in the formed trie else false in the search function. (In case of true, 1 is printed and false, 0 is printed by the driver's code.
Expected Time Complexity: O(M+|search|).
Expected Auxiliary Space: O(M).
M = sum of the length of all strings which is present in the key[] 
|search| denotes the length of the string search.
Constraints:
1 <= N <= 10^{4}
1 <= |input strings|, |A| <= 100

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(M+|search|).
Expected Auxiliary Space: O(M).

Starter code:
#User function Template for python3



"""

class TrieNode: 

      

    def __init__(self): 

        self.children = [None]*26

  

        # isEndOfWord is True if node represent the end of the word 

        self.isEndOfWord = False

"""

#Function to insert string into TRIE.

def insert(root,key):

    

    #code here



#Function to use TRIE data structure and search the given string.

def search(root, key):

    

    #code here

Solutions:
def insert(root, key):
	curr = root
	for char in key:
		index = ord(char) - ord('a')
		if curr.children[index] is None:
			curr.children[index] = TrieNode()
		curr = curr.children[index]
	curr.isEndOfWord = True

def search(root, key):
	curr = root
	for char in key:
		index = ord(char) - ord('a')
		if curr.children[index] is None:
			return False
		curr = curr.children[index]
	return curr.isEndOfWord


def insert(root, key):
	cur = root
	for ch in key:
		index = ord(ch) - ord('a')
		if cur.children[index] == None:
			cur.children[index] = TrieNode()
		cur = cur.children[index]
	cur.isEndOfWord = True

def search(root, key):
	cur = root
	for ch in key:
		index = ord(ch) - ord('a')
		if cur.children[index] == None:
			return False
		cur = cur.children[index]
	return cur.isEndOfWord


def insert(root, key):
	cur = root
	for i in key:
		if cur.children[ord(i) - 97]:
			cur = cur.children[ord(i) - 97]
		else:
			node = TrieNode()
			cur.children[ord(i) - 97] = node
			cur = node
	cur.isEndOfWord = True

def search(root, key):
	cur = root
	for i in key:
		if cur.children[ord(i) - 97]:
			cur = cur.children[ord(i) - 97]
		else:
			return False
	return cur.isEndOfWord


def insert(root, word):
	temp = root
	n = len(word)
	for i in range(n):
		idx = ord(word[i]) - 97
		if temp.children[idx] == None:
			temp.children[idx] = TrieNode()
		temp = temp.children[idx]
	temp.isEndOfWord = 1

def search(root, word):
	temp = root
	n = len(word)
	for i in range(n):
		idx = ord(word[i]) - 97
		if temp.children[idx] == None:
			return 0
		temp = temp.children[idx]
	return temp.isEndOfWord


def insert(root, key):
	for i in key:
		ind = ord(i) - ord('a')
		if root.children[ind] != None:
			root = root.children[ind]
		else:
			root.children[ind] = TrieNode()
			root = root.children[ind]
	root.isEndOfWord = True

def search(root, key):
	for i in key:
		ind = ord(i) - ord('a')
		if root.children[ind] != None:
			root = root.children[ind]
		else:
			return False
	return root.isEndOfWord


def insert(root, key):
	for c in key:
		x = ord(c) - ord('a')
		if root.children[x] != None:
			root = root.children[x]
		else:
			root.children[x] = TrieNode()
			root = root.children[x]
	root.isEndOfWord = True

def search(root, key):
	for c in key:
		x = ord(c) - ord('a')
		if root.children[x] != None:
			root = root.children[x]
		else:
			return False
	return root.isEndOfWord


def insert(root, key):
	curr = root
	for elem in key:
		index = ord(elem) - ord('a')
		if curr.children[index]:
			curr = curr.children[index]
		else:
			curr.children[index] = TrieNode()
			curr = curr.children[index]
	curr.isEndOfWord = True

def search(root, key):
	curr = root
	for elem in key:
		index = ord(elem) - ord('a')
		if not curr.children[index]:
			return 0
		curr = curr.children[index]
	return 1 if curr.isEndOfWord else 0


def insert(root, key):
	temp = root
	for ch in key:
		idx = ord(ch) - ord('a')
		if temp.children[idx] is None:
			temp.children[idx] = TrieNode()
		temp = temp.children[idx]
	else:
		temp.isEndOfWord = True

def search(root, key):
	temp = root
	for ch in key:
		idx = ord(ch) - ord('a')
		if temp.children[idx] is None:
			return False
		temp = temp.children[idx]
	return temp.isEndOfWord


def insert(root, key):
	node = root
	length = len(key)
	for k in range(length):
		index = ord(key[k]) - ord('a')
		if not node.children[index]:
			node.children[index] = TrieNode()
		node = node.children[index]
	node.isEndOfWord = True

def search(root, key):
	node = root
	length = len(key)
	for k in range(length):
		index = ord(key[k]) - ord('a')
		if not node.children[index]:
			return False
		node = node.children[index]
	return node.isEndOfWord


def insert(root, key):
	temp = root
	for ch in key:
		i = charToIndex(ch)
		if temp.children[i] == None:
			temp.children[i] = TrieNode()
		temp = temp.children[i]
	temp.isEndOfWord = True

def search(root, key):
	temp = root
	for ch in key:
		i = charToIndex(ch)
		if temp.children[i] == None:
			return False
		temp = temp.children[i]
	return temp.isEndOfWord


def cti(ch):
	return ord(ch) - ord('a')

def insert(root, key):
	for e in key:
		idx = cti(e)
		if not root.children[idx]:
			root.children[idx] = TrieNode()
		root = root.children[idx]
	root.isEndOfWord = True

def search(root, key):
	for e in key:
		idx = cti(e)
		if not root.children[idx]:
			return
		root = root.children[idx]
	return root.isEndOfWord


def insert(root, key):
	curr = root
	for ele in key:
		ind = ord(ele) - ord('a')
		if curr.children[ind] is None:
			curr.children[ind] = TrieNode()
		curr = curr.children[ind]
	curr.isEndOfWord = True

def search(root, key):
	curr = root
	for ele in key:
		ind = ord(ele) - ord('a')
		if curr.children[ind] is None:
			return False
		curr = curr.children[ind]
	return curr.isEndOfWord


def insert(root, word):
	n = len(word)
	node = root
	for (i, char) in enumerate(word):
		idx = ord(char) - 97
		if node.children[idx] is None:
			newNode = TrieNode()
			if i == n - 1:
				newNode.isEndOfWord = True
			node.children[idx] = newNode
		node = node.children[idx]

def search(root, word):
	n = len(word)
	node = root
	for char in word:
		idx = ord(char) - 97
		if node.children[idx] is None:
			return False
		else:
			node = node.children[idx]
	return node.isEndOfWord


def insert(root, key):
	string = key
	r = root
	cnt = 1
	for i in string:
		if r.children[ord(i) - ord('a')] == None:
			r.children[ord(i) - ord('a')] = TrieNode()
		if cnt == len(string):
			r.isEndOfWord = True
		r = r.children[ord(i) - ord('a')]
		cnt += 1

def search(root, key):
	string = key
	r = root
	cnt = 1
	for i in string:
		if r.children[ord(i) - ord('a')] == None:
			return False
		elif cnt == len(string):
			if r.isEndOfWord == True:
				return True
			else:
				return False
		r = r.children[ord(i) - ord('a')]
		cnt += 1
	return False


def insert(root, key):
	done = False
	if len(key) == 1:
		done = True
	(char, string) = (key[:1], key[1:])
	position = ord(char) - 97
	target_node = root.children[position]
	if target_node is None:
		node = TrieNode()
		node.isEndOfWord = done
		root.children[position] = node
		if done:
			return
		insert(root.children[position], string)
	elif target_node is not None:
		if done:
			target_node.isEndOfWord = target_node.isEndOfWord or done
			return
		insert(target_node, string)

def search(root, key):
	(char, string) = (key[:1], key[1:])
	done = False
	if len(key) == 1:
		done = True
	position = ord(char) - 97
	target_node = root.children[position]
	if target_node is None:
		return False
	else:
		if done:
			return target_node.isEndOfWord
		return search(target_node, string)


def _charToIndex(ch):
	return ord(ch) - ord('a')

def getNode():
	return TrieNode()

def insert(root, key):
	pCrawl = root
	length = len(key)
	for level in range(length):
		index = _charToIndex(key[level])
		if not pCrawl.children[index]:
			pCrawl.children[index] = getNode()
		pCrawl = pCrawl.children[index]
	pCrawl.isEndOfWord = True

def search(root, key):
	pCrawl = root
	length = len(key)
	for level in range(length):
		index = _charToIndex(key[level])
		if not pCrawl.children[index]:
			return False
		pCrawl = pCrawl.children[index]
	return pCrawl.isEndOfWord


def insert(root, key):
	temp = root
	length = len(key)
	for level in range(length):
		index = ord(key[level]) - ord('a')
		if not temp.children[index]:
			temp.children[index] = TrieNode()
		temp = temp.children[index]
	temp.isEndOfWord = True

def search(root, key):
	temp = root
	length = len(key)
	for level in range(length):
		index = ord(key[level]) - ord('a')
		if not temp.children[index]:
			return False
		temp = temp.children[index]
	return temp.isEndOfWord


def insert(root, key):
	curr = root
	for c in key:
		if not curr.children[97 - ord(c)]:
			curr.children[97 - ord(c)] = TrieNode()
		curr = curr.children[97 - ord(c)]
	curr.isEndOfWord = True

def search(root, key):
	curr = root
	for c in key:
		if not curr.children[97 - ord(c)]:
			return False
		curr = curr.children[97 - ord(c)]
	return curr.isEndOfWord


def containkey(root, ch):
	return root.children[ord(ch) - ord('a')] != None

def put(root, ch, node):
	root.children[ord(ch) - ord('a')] = node

def get(root, ch):
	return root.children[ord(ch) - ord('a')]

def insert(root, word):
	node = root
	for i in range(len(word)):
		if containkey(node, word[i]) == False:
			put(node, word[i], TrieNode())
		node = get(node, word[i])
	node.isEndOfWord = True

def isEnd(root):
	return root.isEndOfWord

def search(root, word):
	node = root
	for i in range(len(word)):
		if containkey(node, word[i]) == False:
			return False
		node = get(node, word[i])
	return isEnd(node)


def insert(root, key):
	for ch in key:
		i = ord(ch) - ord('a')
		if not root.children[i]:
			root.children[i] = TrieNode()
		root = root.children[i]
	root.isEndOfWord = True

def search(root, key):
	for ch in key:
		i = ord(ch) - ord('a')
		if not root.children[i]:
			return False
		root = root.children[i]
	return root.isEndOfWord


def insert(root, key):
	cur = root
	for i in range(len(key)):
		c = ord(key[i]) - ord('a')
		if cur.children[c] is None:
			cur.children[c] = TrieNode()
		cur = cur.children[c]
	cur.isEndOfWord = True

def search(root, key):
	cur = root
	for i in range(len(key)):
		c = ord(key[i]) - ord('a')
		if cur.children[c] is None:
			return False
		else:
			cur = cur.children[c]
	return cur.isEndOfWord


def insert(root, key):
	curNode = root
	for i in range(len(key)):
		cur = key[i]
		if not curNode.children[ord(cur) - ord('a')]:
			newNode = TrieNode()
			curNode.children[ord(cur) - ord('a')] = newNode
		curNode = curNode.children[ord(cur) - ord('a')]
	curNode.isEndOfWord = True

def search(root, key):
	curNode = root
	for i in range(len(key)):
		cur = key[i]
		if not curNode.children[ord(cur) - ord('a')]:
			return False
		curNode = curNode.children[ord(cur) - ord('a')]
	return curNode.isEndOfWord


def insert(root, key):
	curr = root
	for ch in key:
		i = ord(ch) - 97
		if curr.children[i] == None:
			curr.children[i] = TrieNode()
		curr = curr.children[i]
	curr.isEndOfWord = True

def search(root, key):
	curr = root
	for ch in key:
		i = ord(ch) - 97
		if curr.children[i] == None:
			return False
		curr = curr.children[i]
	return curr.isEndOfWord


def insert(root, key):
	point = root
	n = len(key)
	for i in range(n):
		index = charToIndex(key[i])
		if not point.children[index]:
			point.children[index] = TrieNode()
		point = point.children[index]
	point.isEndOfWord = True

def search(root, key):
	point = root
	for i in range(len(key)):
		ind = charToIndex(key[i])
		if not point.children[ind]:
			return 0
		point = point.children[ind]
	return point.isEndOfWord


def insert(root, key):
	for i in key:
		ind = ord(i) - ord('a')
		if root.children[ind] != None:
			root = root.children[ind]
		else:
			root.children[ind] = TrieNode()
			root = root.children[ind]
	root.isEndOfWord = 1

def search(root, key):
	for i in key:
		ind = ord(i) - ord('a')
		if root.children[ind] != None:
			root = root.children[ind]
		else:
			return 0
	return root.isEndOfWord


def insert(root, key):
	for letter in key:
		index = charToIndex(letter)
		if not root.children[index]:
			root.children[index] = TrieNode()
		root = root.children[index]
	root.isEndOfWord = True

def search(root, key):
	for letter in key:
		index = charToIndex(letter)
		if not root.children[index]:
			return False
		root = root.children[index]
	return root.isEndOfWord


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

def insert(root, key):
	current = root
	for i in range(len(key)):
		index = ord(key[i]) - ord('a')
		if not current.children[index]:
			current.children[index] = TrieNode()
		current = current.children[index]
	current.isEndOfWord = True

def search(root, key):
	current = root
	for i in range(len(key)):
		index = ord(key[i]) - ord('a')
		if not current.children[index]:
			return False
		current = current.children[index]
	return current.isEndOfWord


def insert(root, key):
	if not key:
		root.isEndOfWord = True
	index = charToIndex(key[0])
	if root.children[index] is None:
		root.children[index] = TrieNode()
	if len(key) == 1:
		root.children[index].isEndOfWord = True
		return
	insert(root.children[index], key[1:])

def search(root, key):
	if not root:
		return 0
	if not key:
		return 1 if root.isEndOfWord else 0
	index = charToIndex(key[0])
	if root.children[index]:
		return search(root.children[index], key[1:])
	return 0


def insert(root, key):
	for w in key:
		if root.children[ord(w) - ord('a')] == None:
			root.children[ord(w) - ord('a')] = TrieNode()
		root = root.children[ord(w) - ord('a')]
	root.isEndOfWord = True

def search(root, key):
	for w in key:
		if root.children[ord(w) - ord('a')] == None:
			return False
		root = root.children[ord(w) - ord('a')]
	return root.isEndOfWord


def insert(root, key):
	for k in key:
		index = ord(k) - 97
		if root.children[index] == None:
			root.children[index] = TrieNode()
		root = root.children[index]
	root.isEndOfWord = True

def search(root, key):
	for i in range(len(key)):
		index = ord(key[i]) - 97
		if root.children[index] == None:
			return False
		root = root.children[index]
	if root.isEndOfWord == True:
		return True
	else:
		return False


def insert(root, word):
	if len(word) == 0:
		root.isEndOfWord = True
		return
	ci = ord(word[0]) - ord('a')
	child = root.children[ci]
	if not child:
		child = TrieNode()
		root.children[ci] = child
	insert(child, word[1:])

def search(root, word):
	if len(word) == 0 and root.isEndOfWord == True:
		return True
	if len(word) == 0:
		return False
	ci = ord(word[0]) - ord('a')
	child = root.children[ci]
	if not child:
		return False
	return search(child, word[1:])


def insert(root, key):
	for c in key:
		idx = ord(c) - ord('a')
		if root.children[idx] is None:
			root.children[idx] = TrieNode()
		root = root.children[idx]
	root.isEndOfWord = True

def search(root, key):
	for c in key:
		idx = ord(c) - ord('a')
		if root.children[idx] is None:
			return False
		root = root.children[idx]
	return root.isEndOfWord


def insert(root, key):
	node = root
	for c in key:
		idx = ord(c) - ord('a')
		node.children[idx] = node.children[idx] or TrieNode()
		node = node.children[idx]
	node.isEndOfWord = True

def search(root, key):
	node = root
	for c in key:
		idx = ord(c) - ord('a')
		node = node.children[idx]
		if node is None:
			return 0
	return int(node.isEndOfWord)


def insert(root, key):
	if key == '':
		root.isEndOfWord = True
		return
	else:
		ind = ord(key[0]) - 97
		if root.children[ind] == None:
			root.children[ind] = TrieNode()
		root = root.children[ind]
		insert(root, key[1:])

def search(root, key):
	if key == '':
		return root.isEndOfWord
	else:
		ind = ord(key[0]) - 97
		if root.children[ind] == None:
			return False
		root = root.children[ind]
		return search(root, key[1:])


def insert(root, key):
	curNode = root
	for i in range(len(key)):
		idx = ord(key[i]) - ord('a')
		if curNode.children[idx] == None:
			curNode.children[idx] = TrieNode()
		curNode = curNode.children[idx]
	curNode.isEndOfWord = True

def search(root, key):
	curNode = root
	for i in range(len(key)):
		idx = ord(key[i]) - ord('a')
		if curNode.children[idx] == None:
			return False
		curNode = curNode.children[idx]
	return curNode.isEndOfWord


def insert(root, key):
	n = len(key)
	cur = root
	for i in range(len(key)):
		k = key[i]
		if cur.children[ord(k) - ord('a')] == None:
			cur.children[ord(k) - ord('a')] = TrieNode()
		cur = cur.children[ord(k) - ord('a')]
	cur.isEndOfWord = True

def search(root, key):
	n = len(key)
	cur = root
	for i in range(len(key)):
		k = key[i]
		if cur.children[ord(k) - ord('a')] == None:
			return False
		cur = cur.children[ord(k) - ord('a')]
	return cur.isEndOfWord


def insert(root, key):
	curr = root
	for i in key:
		idx = ord(i) - ord('a')
		if not curr.children[idx]:
			curr.children[idx] = TrieNode()
		curr = curr.children[idx]
	curr.isEndOfWord = True

def search(root, key):
	curr = root
	for i in key:
		idx = ord(i) - ord('a')
		if not curr.children[idx]:
			return False
		else:
			curr = curr.children[idx]
	if curr.isEndOfWord:
		return True
	else:
		return False


def insert(root, key):
	node = root
	for i in key:
		if not node.children[charToIndex(i)]:
			temp = TrieNode()
			node.children[charToIndex(i)] = temp
		node = node.children[charToIndex(i)]
	node.isEndOfWord = True

def search(root, key):
	node = root
	for i in key:
		if not node:
			return False
		node = node.children[charToIndex(i)]
	if node and node.isEndOfWord:
		return True
	return False


def insert(root, key):
	curr = root
	for i in key:
		ind = charToIndex(i)
		if not curr.children[ind]:
			curr.children[ind] = TrieNode()
		curr = curr.children[ind]
	curr.isEndOfWord = True

def search(root, key):
	curr = root
	for i in key:
		ind = charToIndex(i)
		if not curr.children[ind]:
			return False
		curr = curr.children[ind]
	return curr.isEndOfWord


def insert(root, key):
	if len(key) == 0:
		root.isEndOfWord = True
		return
	letter = key[0]
	key = key[1:]
	pos = ord(letter) - ord('a')
	if root.children[pos] is None:
		root.children[pos] = TrieNode()
	insert(root.children[pos], key)

def search(root, key):
	if len(key) == 0:
		return root.isEndOfWord
	letter = key[0]
	key = key[1:]
	pos = ord(letter) - ord('a')
	if root.children[pos] is None:
		return False
	return search(root.children[pos], key)


def insert(root, key):
	node = root
	for v in key:
		index = ord(v) - ord('a')
		if not node.children[index]:
			node.children[index] = TrieNode()
		node = node.children[index]
	node.isEndOfWord = True

def search(root, key):
	node = root
	for v in key:
		index = ord(v) - ord('a')
		if not node.children[index]:
			return False
		node = node.children[index]
	return node.isEndOfWord


def insert(root, key):
	cur = root
	for (i, ch) in enumerate(key):
		if cur.children[ord(ch) - ord('a')] is None:
			node = TrieNode()
			cur.children[ord(ch) - ord('a')] = node
		node = cur.children[ord(ch) - ord('a')]
		if i == len(key) - 1:
			node.isEndOfWord = 1
		cur = node
	return

def search(root, key):
	cur = root
	if not root:
		return 0
	for (i, ch) in enumerate(key):
		if cur.children[ord(ch) - ord('a')] is None:
			return 0
		elif i == len(key) - 1:
			if cur.children[ord(ch) - ord('a')].isEndOfWord == 1:
				return 1
			else:
				return 0
		cur = cur.children[ord(ch) - ord('a')]


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

def insert(root, key):
	for c in key:
		idx = ord(c) - ord('a')
		if root.children[idx] is None:
			root.children[idx] = TrieNode()
		root = root.children[idx]
	root.isEndOfWord = True

def search(root, key):
	for c in key:
		idx = ord(c) - ord('a')
		if root.children[idx] is None:
			return False
		root = root.children[idx]
	return root.isEndOfWord


def get_pos(c):
	return ord(c) - ord('a')

def insert(root, key):
	p = root
	for c in key:
		pos = get_pos(c)
		if p.children[pos] is None:
			p.children[pos] = TrieNode()
		p = p.children[pos]
	p.isEndOfWord = True

def search(root, key):
	p = root
	for c in key:
		pos = get_pos(c)
		if p.children[pos] is None:
			return False
		p = p.children[pos]
	return p.isEndOfWord


def insert(root, key):
	cur = root
	index = 0
	n = len(key)
	while index < n:
		i = ord(key[index]) - ord('a')
		if cur.children[i] == None:
			node = TrieNode()
			cur.children[i] = node
		cur = cur.children[i]
		index = index + 1
	cur.isEndOfWord = True

def search(root, key):
	cur = root
	for (index, ch) in enumerate(key):
		i = ord(ch) - ord('a')
		if cur.children[i] == None:
			return 0
		cur = cur.children[i]
		if index == len(key) - 1 and cur.isEndOfWord == False:
			return 0
	return 1


def insert(root, strg):
	curr = root
	for i in range(len(strg)):
		ind = ord(strg[i]) - 97
		if curr.children[ind] == None:
			curr.children[ind] = TrieNode()
		curr = curr.children[ind]
	curr.isEndOfWord = True

def search(root, strg):
	curr = root
	for i in range(len(strg)):
		ind = ord(strg[i]) - 97
		if curr.children[ind] == None:
			return False
		curr = curr.children[ind]
	return curr.isEndOfWord


def __init__(self):
	self.root = self.getNode()

def getNode():
	return TrieNode()

def chartoindex(ch):
	return ord(ch) - ord('a')

def insert(root, key):
	newnode = root
	for i in range(len(key)):
		index = chartoindex(key[i])
		if not newnode.children[index]:
			newnode.children[index] = getNode()
		newnode = newnode.children[index]
	newnode.isEndOfWord = True

def search(root, key):
	newnode = root
	for i in range(len(key)):
		index = chartoindex(key[i])
		if not newnode.children[index]:
			return False
		newnode = newnode.children[index]
	return newnode.isEndOfWord


def insert(root, key):
	for i in range(len(key)):
		v = charToIndex(key[i])
		if root.children[v]:
			root = root.children[v]
		else:
			root.children[v] = TrieNode()
			root = root.children[v]
	root.isEndOfWord = True

def search(root, key):
	for i in range(len(key)):
		v = charToIndex(key[i])
		if root.children[v]:
			root = root.children[v]
		else:
			return 0
	return root.isEndOfWord


def insert(root, key):
	for k in key:
		index = ord(k) - 97
		if not root.children[index]:
			root.children[index] = TrieNode()
		root = root.children[index]
	root.isEndOfWord = True

def search(root, key):
	for k in key:
		index = ord(k) - 97
		if not root.children[index]:
			return False
		root = root.children[index]
	return root.isEndOfWord


def insert(root, key):
	curr = root
	for letter in key:
		ind = ord(letter) - 97
		if not curr.children[ind]:
			curr.children[ind] = TrieNode()
		curr = curr.children[ind]
	curr.isEndOfWord = True

def search(root, key):
	curr = root
	for letter in key:
		ind = ord(letter) - 97
		if curr.children[ind]:
			curr = curr.children[ind]
		else:
			return False
	return curr.isEndOfWord


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

def insert(root, key):
	if len(key) == 0:
		root.isEndOfWord = True
		return
	index = ord(key[0]) - ord('a')
	node = TrieNode()
	if root.children[index]:
		node = root.children[index]
	else:
		root.children[index] = node
	insert(node, key[1:])

def search(root, key):
	if len(key) == 0:
		return root.isEndOfWord
	index = ord(key[0]) - ord('a')
	if root.children[index]:
		return search(root.children[index], key[1:])
	else:
		return False


def insert(root, key):
	length = len(key)
	for i in range(length):
		index = ord(key[i]) - ord('a')
		if root.children[index] is None:
			root.children[index] = TrieNode()
		root = root.children[index]
	root.isEndOfWord = True

def search(root, key):
	length = len(key)
	for i in range(length):
		index = ord(key[i]) - ord('a')
		if root.children[index] == None:
			return 0
		root = root.children[index]
	if root.isEndOfWord == True:
		return 1
	else:
		return 0


def retIdx(c):
	return ord(c) - ord('a')

def insert(root, key):
	cur = root
	for c in key:
		idx = retIdx(c)
		if not cur.children[idx]:
			cur.children[idx] = TrieNode()
		cur = cur.children[idx]
	cur.isEndOfWord = True

def search(root, key):
	cur = root
	for c in key:
		idx = retIdx(c)
		if not cur.children[idx]:
			return False
		cur = cur.children[idx]
	return True if cur.isEndOfWord else False


def insert(root, key):
	cur = root
	for i in key:
		ch = ord(i) - ord('a')
		if cur.children[ch] == None:
			cur.children[ch] = TrieNode()
		cur = cur.children[ch]
	cur.isEndOfWord = True

def search(root, key):
	cur = root
	for i in key:
		ch = ord(i) - ord('a')
		if cur.children[ch] == None:
			return 0
		else:
			cur = cur.children[ch]
	if cur.isEndOfWord:
		return 1
	return 0


def insert(root, key):
	cur = root
	n = len(key)
	for i in range(n):
		g = ord(key[i]) - 97
		if cur.children[g] is None:
			h = TrieNode()
			cur.children[g] = h
		if i == n - 1:
			cur.isEndOfWord = True
		cur = cur.children[g]

def search(root, key):
	cur = root
	n = len(key)
	for i in range(n):
		g = ord(key[i]) - 97
		if cur.children[g] is None:
			return False
		if i == n - 1:
			if cur.isEndOfWord:
				return True
			else:
				return False
		cur = cur.children[g]


def insert(root, key):
	node = root
	for i in key:
		ind = ord(i) - ord('a')
		if node.children[ind] is None:
			temp = TrieNode()
			node.children[ind] = temp
		node = node.children[ind]
	node.isEndOfWord = True

def search(root, key):
	node = root
	for i in key:
		ind = ord(i) - ord('a')
		if node.children[ind] is None:
			return False
		node = node.children[ind]
	if node.isEndOfWord == True:
		return True
	return False


def insert(root, key):
	pCrawl = root
	length = len(key)
	for level in range(length):
		index = charToIndex(key[level])
		if not pCrawl.children[index]:
			pCrawl.children[index] = TrieNode()
		pCrawl = pCrawl.children[index]
	pCrawl.isEndOfWord = True

def search(root, key):
	pCrawl = root
	length = len(key)
	for level in range(length):
		index = charToIndex(key[level])
		if not pCrawl.children[index]:
			return False
		pCrawl = pCrawl.children[index]
	return pCrawl.isEndOfWord


def insert(root, key):
	curr = root
	for char in key:
		pos = ord('a') - ord(char)
		if curr.children[pos] == None:
			curr.children[pos] = TrieNode()
			curr = curr.children[pos]
		else:
			curr = curr.children[pos]
	curr.isEndOfWord = True

def search(root, key):
	curr = root
	for char in key:
		pos = ord('a') - ord(char)
		if curr.children[pos] == None:
			return False
		curr = curr.children[pos]
	return curr.isEndOfWord