Trie is an efficient information retrieval data structure. This data structure is used to store Strings and search strings, String stored can also be deleted. Given a Trie root for a larger string super and a string key, delete all the occurences of key in the Trie.
Example 1:
Input:
N = 8
super = "the a there answer any by bye their" 
key = "the" 
 
Your Task:
Complete the function deleteKey() to delete the given string key.The String key if exists in the larger string super, must be deleted from Trie root. The larger string super contains space separated small strings. And if the string is deleted successfully than 1 will be printed.
If any other string other than String A is deleted, you will get wrong answer.
 
Constraints:
1≤ T ≤200
1≤ N, |A| ≤20

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:
#User function Template for python3



class Solution():

    def deleteKey(self, root, key):

        #your code goes here

Solutions:
class Solution:

	def deleteKey(self, root, key):
		curr = root
		for c in key:
			idx = ord(c) - ord('a')
			if curr.children[idx] != None:
				curr = curr.children[idx]
		curr.isEndOfWord = False


class Solution:

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


class Solution:

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


class Solution:

	def deleteKey(self, root, key):
		self.remove(key, root)

	def remove(self, word, node, depth=0):
		if not node:
			return None
		if depth == len(word):
			return self.getUpdatedLastNodeOfRemovedWord(node)
		else:
			index = self.getIndexForLetter(word[depth])
			node.children[index] = self.remove(word, node.children[index], depth + 1)
		if self.isEmpty(node) and (not node.isEndOfWord):
			del node
			node = None
		return node

	def getUpdatedLastNodeOfRemovedWord(self, lastNode):
		lastNode.isEndOfWord = False
		if self.isEmpty(lastNode):
			del lastNode
			lastNode = None
		return lastNode

	def getIndexForLetter(self, letter):
		return ord(letter) - ord('a')

	def isEmpty(self, node):
		for i in range(26):
			if node.children[i]:
				return False
		return True


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

class Solution:

	def deleteKey(self, root, key):
		curr = root
		for c in key:
			idx = chartoindex(c)
			if curr.children[idx]:
				curr = curr.children[idx]
		curr.isEndOfWord = False


class Solution:

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

	def has_child(self, root):
		for (i, child) in enumerate(root.children):
			if child is not None:
				return True
		return False

	def solve(self, root, key, i):
		if i == len(key):
			if root.isEndOfWord:
				root.isEndOfWord = False
			if not self.has_child(root):
				del root
			return
		idx = ord(key[i]) - ord('a')
		self.solve(root.children[idx], key, i + 1)
		if not root.isEndOfWord and (not self.has_child(root)):
			del root

	def deleteKey(self, root, key):
		self.solve(root, key, 0)


class Solution:

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


class Solution:

	def deleteKey(self, root, key):
		curr = root
		for ch in key:
			i = charToIndex(ch)
			if curr.children[i]:
				curr = curr.children[i]
		curr.isEndOfWord = False


class Solution:

	def deleteKey(self, root, key):
		for e in key:
			idx = ord(e) - ord('a')
			if not root.children[idx]:
				return
			root = root.children[idx]
		root.isEndOfWord = False


class Solution:

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


class Solution:

	def has_child(self, root):
		if root is None:
			return False
		for child in root.children:
			if child is not None:
				return True
		return False

	def solve(self, root, key, depth):
		if root is None:
			return
		if len(key) == depth:
			if root.isEndOfWord:
				root.isEndOfWord = False
			if not self.has_child(root) == 0:
				del root
				root = None
			return root
		idx = ord(key[depth]) - ord('a')
		root.children[idx] = self.solve(root.children[idx], key, depth + 1)
		if root and (not self.has_child(root)) and (not root.isEndOfWord):
			del root
			root = None
		return root

	def deleteKey(self, root, key):
		self.solve(root, key, 0)


class Solution:

	def deleteKey(self, root, key):

		def empty(n):
			return all((c is None for c in n.children))

		def remove(n, key, i):
			if not n:
				return False
			if i == len(key):
				n.isEndOfWord = False
				return empty(n)
			id = ord(key[i]) - ord('a')
			if remove(n.children[id], key, i + 1):
				n.children[id] = None
				return True
			else:
				return False
		return remove(root, key, 0)


class Solution:

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


class Solution:

	def deleteKey(self, root, key):
		pointer = root
		for currChar in key:
			charIndex = ord(currChar) - ord('a')
			if pointer.children[charIndex] == None:
				return root
			pointer = pointer.children[charIndex]
		pointer.isEndOfWord = False
		return root


class Solution:

	def deleteKey(self, root, key):

		def isempty(node):
			for i in node.children:
				if i != None:
					return False
			return True

		def delete(node, key, i=0):
			if node == None:
				return
			if len(key) == i:
				if node.isEndOfWord:
					node.isEndOfWord = False
				if isempty(node):
					return None
				return node
			ind = ord(key[i]) - ord('a')
			node.children[ind] = delete(node.children[ind], key, i + 1)
			if isempty(node) and node.isEndOfWord == False:
				return None
			return node
		delete(root, key)


class Solution:

	def deleteKey(self, root, key):

		def empty(root):
			for i in range(26):
				if root.children[i]:
					return False
			return True

		def delete(root, key, d):
			if not root:
				return False
			if d == len(key):
				root.isEndOfWord = False
				return empty(root)
			ind = ord(key[d]) - ord('a')
			if delete(root.children[ind], key, d + 1):
				root.children[ind] = None
				return True
			else:
				return False
		return delete(root, key, 0)


class Solution:

	def is_empty(self, root):
		for i in range(26):
			if root.children[i]:
				return False
		return True

	def deleteKey(self, root, key, depth=0):
		try:
			if root is None:
				return
			if len(key) == depth:
				if root.isEndOfWord:
					root.isEndOfWord = False
				if self.is_empty(root):
					del root
					root = None
				return root
			idx = ord(key[depth]) - ord('a')
			root.children[idx] = self.deleteKey(root.children[idx], key, depth + 1)
			if root and self.is_empty(root) and (not root.isEndOfWord):
				del root
				root = None
			return root
		except Exception as e:
			print(e)


class Solution:

	def deleteKey(self, root, key):
		for c in key:
			idx = ord(c) - 97
			root = root.children[idx]
		root.isEndOfWord = False


class Solution:

	def deleteKey(self, root, key):
		self.dele(root, key, 0)

	def dele(self, root, key, i):
		if i == len(key):
			return
		index = ord(key[i]) - ord('a')
		if not root.children[index]:
			return
		self.dele(root.children[index], key, i + 1)
		x = set(root.children[index].children)
		if len(x) > 1:
			root.children[index].isEndOfWord = False
		else:
			root.children[index] = None


class Solution:

	def deleteKey(self, root, key):
		curr = root
		for ch in key:
			i = ord(ch) - ord('a')
			if curr.children[i]:
				curr = curr.children[i]
		curr.isEndOfWord = False


class Solution:

	def deleteKey(self, root, key):

		def empty(n):
			for i in range(26):
				if n.children[i]:
					return False
			return True

		def remove(n, key, i):
			if i == len(key):
				n.isEndOfWord = False
				return empty(n) == 0
			id = ord(key[i]) - ord('a')
			if remove(n.children[id], key, i + 1):
				n.children[id] = None
				return True
			else:
				return False
		return remove(root, key, 0)


class Solution:

	def deleteKey(self, root, key):
		cur = root
		for c in key:
			id = ord(c) - ord('a')
			cur = cur.children[id]
		cur.isEndOfWord = False


class Solution:

	def delete(self, node, s, i):
		if i == len(s):
			if node.isEndOfWord == True:
				node.isEndOfWord = False
			return
		self.delete(node.children[ord(s[i]) - 97], s, i + 1)
		x = 0
		for j in node.children:
			if j != None:
				x += 1
		if x == 1:
			node.children[ord(s[i]) - 97] = None
		return

	def deleteKey(self, root, key):
		self.delete(root, key, 0)


class Solution:

	def deleteKey(self, root, key):
		curr = root
		for e in key:
			idx = charToIndex(e)
			if curr.children[idx]:
				curr = curr.children[idx]
		curr.isEndOfWord = False


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

def child_count(node):
	return sum((1 for child in node.children if child))

class Solution:

	def deleteKey(self, root, key):
		last_node = (root, idx(key[0]))
		node = root
		for c in key:
			i = idx(c)
			if child_count(node) > 1:
				last_node = (node, i)
			node = node.children[i]
			if node is None:
				return
		node.isEndOfWord = False
		i = last_node[1]
		last_node[0].children[i] = None
		return


class Solution:

	def delete(self, CurrNode, key, pos):
		if CurrNode == None:
			return
		if pos == len(key):
			CurrNode.isEndOfWord = False
			return
		self.delete(CurrNode.children[ord(key[pos]) - ord('a')], key, pos + 1)

	def deleteKey(self, root, key):
		self.delete(root, key, 0)


class Solution:

	def deleteKey(self, root, key):
		temp = root
		for ele in key:
			if temp.children[ord(ele) - ord('a')]:
				temp = temp.children[ord(ele) - ord('a')]
			else:
				return
		temp.isEndOfWord = False


class Solution:

	def deleteKey(self, root, key):
		for i in range(len(key)):
			if root.children[ord(key[i]) - ord('a')] != None:
				root = root.children[ord(key[i]) - ord('a')]
		root.isEndOfWord = False


class Solution:

	def _isEmpty(self, root):
		for child in root.children:
			if child != None:
				return False
		return True

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

	def _deleteKey(self, root, key):
		print('key:', key)
		if root == None:
			return (-1, -1)
		index = ord(key[0]) - ord('a')
		if len(key) == 1:
			if root.children[index] == None or root.children[index].isEndOfWord == False:
				print('Word not found')
				return (-1, -1)
			child = root.children[index]
			if self._isEmpty(child):
				print('Word found delete all')
				root.children[index] = None
				return (0, 0)
			else:
				print('Word found Dont delete', index)
				child.isEndofWord = False
				print(index, root and root.children[index] != None)
				return (0, -1)
		else:
			if root.children[index] == None:
				return (-1, -1)
			(found, delete) = self.deleteKey(root.children[index], key[1:])
			if delete == 0:
				root.children[index] = None
			print(index, root and root.children[index] != None)
			return (found, delete)


class Solution:

	def deleteKey(self, root, key):
		ki = 0
		ke = len(key)
		snode = []
		while root and root.isEndOfWord == False:
			v = charToIndex(key[ki])
			if root.children[v]:
				snode.append([root, v])
				root = root.children[v]
				ki += 1
				if ki == ke:
					for n in snode:
						n[0].children[n[1]] = None
					ki = 0
			else:
				next = None
				for c in root.children:
					if c:
						next = c
						break
				ki = 0
				snode = []
				root = next


class Solution:

	def deleteKey(self, root, key):
		for k in key:
			index = ord(k) - 97
			root = root.children[index]
		root.isEndOfWord = False


class Solution:

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


class Solution:

	def deleteKey(self, root, key):
		a = ord('a')
		for i in key:
			if root.children[ord(i) - a] == None:
				return False
			root = root.children[ord(i) - a]
		if root.isEndOfWord == False:
			return 0
		root.isEndOfWord = False
		return True


class Solution:

	def deleteKey(self, root, key):
		node = root
		for i in key:
			node = node.children[ord(i) - ord('a')]
		node.isEndOfWord = False


class Solution:

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


class Solution:

	def deleteKey(self, root, key):
		node = root
		for i in key:
			count = 0
			for j in node.children:
				if j is None:
					count += 1
			ind = ord(i) - ord('a')
			if count < 25:
				node = node.children[ind]
			if count == 25:
				node.children[ind] = None
		node.isEndOfWord = False


class Solution:

	def deleteKey(self, root, key):
		curr = root
		for l in key:
			idx = charToIndex(l)
			if not curr.children[idx]:
				return
			curr = curr.children[idx]
		curr.isEndOfWord = False


class Solution:

	def deleteKey(self, root, key):
		n = len(key)
		cur = root
		stacks = [cur]
		for i in range(n):
			idx = charToIndex(key[i])
			if cur.children[idx] is None:
				return
			else:
				cur = cur.children[idx]
				stacks.append(cur)
				if i == n - 1 and cur.isEndOfWord:
					n_not_none = 0
					for j in range(26):
						if cur.children[j] is not None:
							n_not_none += 1
					if n_not_none > 0:
						cur.isEndOfWord = False
					else:
						stacks.pop()
						reverse_idx = n - 1
						while stacks:
							top = stacks.pop()
							reverse_id = charToIndex(key[reverse_idx])
							if top.isEndOfWord:
								top.children[reverse_id] = None
								break
							else:
								n_not_none = 0
								for j in range(26):
									if cur.children[j] is not None:
										n_not_none += 1
								if n_not_none == 1:
									top.children[reverse_id] = None
									reverse_id -= 1
								else:
									top.children[reverse_id] = None
									break
					return


class Solution:

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


class Solution:

	def deleteKey(self, root, key):

		def delete(i, key, root):
			if i == len(key) and root.isEndOfWord:
				root.isEndOfWord = False
				return root.children
			idx = ord(key[i]) - ord('a')
			if root.children[idx]:
				root = delete(i + 1, key, root.children[idx])
			return root
		delete(0, key, root)


class Solution:

	def deleteKey(self, root, key):
		curr = root
		for ele in key:
			if not curr.children[ord(ele) - ord('a')]:
				return
			curr = curr.children[ord(ele) - ord('a')]
		curr.isEndOfWord = False


class Solution:

	def deleteKey(self, root, key):

		def delete(word, pos, root):
			if not root:
				return
			if pos == len(word):
				if root.isEndOfWord:
					root.isEndOfWord = False
					return
			delete(word, pos + 1, root.children[ord(word[pos]) - ord('a')])
		delete(key, 0, root)


class Solution:

	def deleteKey(self, root, key):
		node = root
		size = len(key)
		for i in range(size):
			index = charToIndex(key[i])
			if node.children[index]:
				node = node.children[index]
		node.isEndOfWord = False


class Solution:

	def cti(self, c: str):
		return ord(c) - ord('a')

	def deleteKey(self, root, key):
		for c in key:
			index = self.cti(c)
			if not root.children[index]:
				return
			root = root.children[index]
		root.isEndOfWord = False


class Solution:

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


class Solution:

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


class Solution:

	def deleteKey(self, root, key):
		if root != None:
			if len(key) == 0:
				root.isEndOfWord = 0
			else:
				self.deleteKey(root.children[ord(key[0]) - 97], key[1:])


class Solution:

	def deleteKey(self, root, key):
		node = root
		for c in key:
			index = charToIndex(c)
			node = node.children[index]
		node.isEndOfWord = False


class Solution:

	def deleteKey(self, root, key):
		curr = root
		for ch in key:
			if curr.children[ord(ch) - ord('a')] is None:
				return root
			else:
				curr = curr.children[ord(ch) - ord('a')]
		if curr.isEndOfWord:
			curr.isEndOfWord = False
		return root


class Solution:

	def deleteKey(self, root, key):

		def isEmpty(r):
			for c in r.children:
				if c:
					return False
			return True

		def deleteK(r, k, depth):
			if not r:
				return None
			if depth == len(k):
				if r.isEndOfWord:
					r.isEndOfWord = False
				if isEmpty(r):
					del r
					r = None
				return r
			r.children[ord(k[depth]) - 97] = deleteK(r.children[ord(k[depth]) - 97], k, depth + 1)
			if isEmpty(r) and r.isEndOfWord == False:
				del r
				r = None
			return r
		deleteK(root, key, 0)


class Solution:

	def deleteKey(self, root, key):
		temp = root
		level = 0
		if search(root, key):
			while level < len(key) and temp.children[ord(key[level]) - 97]:
				temp = temp.children[ord(key[level]) - 97]
				level += 1
			temp.isEndOfWord = False


class Solution:

	def deleteKey(self, root, key):
		depth = 0
		self.delete(root, key, depth)

	def delete(self, root, key, depth):
		if root == None:
			return None
		if len(key) == depth:
			if root.isEndOfWord == True:
				root.isEndOfWord = False
			if self.isEmpty(root):
				root = None
			return root
		index = ord(key[depth]) - ord('a')
		root.children[index] = self.delete(root.children[index], key, depth + 1)
		if self.isEmpty(root) and root.isEndOfWord == False:
			return None
		return root

	def isEmpty(self, node):
		for i in range(len(node.children)):
			if node.children[i] != None:
				return False
		return True


def c2i(s):
	return ord(s) - ord('a')

class Solution:

	def deleteKey(self, root, key):
		pCrawl = root
		length = len(key)
		for level in range(length):
			index = c2i(key[level])
			if pCrawl.children[index] is None:
				return
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = False

class TrieNode:

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

class Trie:

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

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

def insert(root, key):
	for e in key:
		idx = charToIndex(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 = charToIndex(e)
		if not root.children[idx]:
			return
		root = root.children[idx]
	return root.isEndOfWord
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		n = int(input())
		arr = input().strip().split()
		key = input()
		t = Trie()
		for s in arr:
			insert(t.root, s)
		Solution().deleteKey(t.root, key)
		if search(t.root, key):
			print(0)
		else:
			print(1)


class Solution:

	def deleteKey(self, root, word):
		ROOT = root
		stack = []
		for w in word:
			index = ord(w) - ord('a')
			if not root.children[index]:
				return False
			stack.append(root)
			root = root.children[index]
		if any(root.children):
			root.isEndOfWord = False
		else:
			while stack:
				for i in range(26):
					if stack[-1].children[i] == root:
						break
				if stack[-1].children[i] and root.isEndOfWord:
					stack[-1].children[i] = None
				if stack[-1].isEndOfWord == True:
					break
				root = stack.pop()

class TrieNode:

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

class Trie:

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

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

def insert(root, key):
	for e in key:
		idx = charToIndex(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 = charToIndex(e)
		if not root.children[idx]:
			return
		root = root.children[idx]
	return root.isEndOfWord
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		n = int(input())
		arr = input().strip().split()
		key = input()
		t = Trie()
		for s in arr:
			insert(t.root, s)
		Solution().deleteKey(t.root, key)
		if search(t.root, key):
			print(0)
		else:
			print(1)


class Solution:

	def _util(self, root, key, i):
		if not root:
			return None
		if i == len(key):
			root.isEndOfWord = False
			if self.isEmpty(root):
				root = None
			return root
		index = charToIndex(key[i])
		root.children[index] = self._util(root.children[index], key, i + 1)
		if self.isEmpty(root) and root.isEndOfWord == False:
			root = None

	def isEmpty(self, root):
		for i in range(26):
			if root.children[i] != None:
				return False
		return True

	def deleteKey(self, root, key):
		return self._util(root, key, 0)

class TrieNode:

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

class Trie:

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

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

def insert(root, key):
	for e in key:
		idx = charToIndex(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 = charToIndex(e)
		if not root.children[idx]:
			return
		root = root.children[idx]
	return root.isEndOfWord
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		n = int(input())
		arr = input().strip().split()
		key = input()
		t = Trie()
		for s in arr:
			insert(t.root, s)
		Solution().deleteKey(t.root, key)
		if search(t.root, key):
			print(0)
		else:
			print(1)


class Solution:

	def deleteKey(self, root, key):
		length = len(key)

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


class Solution:

	def deleteKey(self, root, key):
		if len(key) == 0:
			if root.isEndOfWord:
				root.isEndOfWord = False
				return True
			return False
		index = ord(key[0]) - ord('a')
		if root.children[index] is not None:
			child = root.children[index]
		else:
			return False
		return self.deleteKey(child, key[1:])


class Solution:

	def deleteKey(self, root, key):
		curr = root
		for w in key:
			ind = ord(w) - ord('a')
			if curr.children[ind] != None:
				curr.children[ind] = None


class Solution:

	def deleteKey(self, root, key):
		return self.deleteUtil(root, key, 0)

	def deleteUtil(self, root, word, depth):
		if root is None:
			return None
		if depth == len(word):
			if root.isEndOfWord == True:
				root.isEndOfWord = False
			isPrefix = False
			for node in root.children:
				if node is not None:
					isPrefix = True
			if not isPrefix:
				root = None
			return root
		index = charToIndex(word[depth])
		root.children[index] = self.deleteUtil(root.children[index], word, depth + 1)
		isPrefix = False
		for node in root.children:
			if node is not None:
				isPrefix = True
				break
		if not isPrefix and root.isEndOfWord == False:
			root = None
		return root


class Solution:

	def _deleteKey(self, root, key, index):
		if not root or index >= len(key):
			return
		newRoot = root.children[charToIndex(key[index])]
		self._deleteKey(newRoot, key, index + 1)
		if index == len(key) - 1 and newRoot.isEndOfWord:
			newRoot.isEndOfWord = False
		if self.isEmpty(root):
			root.children[charToIndex(key[index])] = None

	def isEmpty(self, root):
		count = 0
		for i in range(len(root.children)):
			if root.children[i]:
				count += 1
			if count > 1:
				return False
		return True

	def deleteKey(self, root, key):
		self._deleteKey(root, key, 0)


class Solution:

	def deleteKey(self, root, key):
		current = root
		for char in key:
			current = current.children[charToIndex(char)]
		current.isEndOfWord = False