<jupyter_start><jupyter_text><jupyter_code>class TrieNode(object):
    def __init__(self,char = ''):
      self.char = char
      self.is_end_word = False
      self.children = [None]*26


class Trie(object):
    def __init__(self):
        self.root = TrieNode()

    def get_index(self,char):
        return ord(char) - ord('a')

    def insert(self,key):
      if not key:
        print('Empty Key!')

      curr = self.root
      key = key.lower()
      for char in key:
        index = self.get_index(char)

        if not curr.children[index]:
            curr.children[index] = TrieNode(char)
        curr = curr.children[index]

      curr.is_end_word = True
      print(key+' inserted!')

    def search(self,key):
      if not key:
        print('Empty Key!')
        return False

      curr = self.root
      key = key.lower()
      for char in key:
        index = self.get_index(char)

        if not curr.children[index]:
            print('Key does not exist!')
            return False
        curr = curr.children[index]

      if curr and curr.is_end_word:
        print('Key Found!')
        return True

      print('Key does not exist!')
      return False
  
    def has_children(self,node):

        for i in range(len(node.children)):
            if node.children[i]:
              return True

        return False

    def delete_helper(self,key,node,length,level):
        delete_self = False
        if not node:
            print('Key does not exist!')
            return False

        if length == level:

            if not self.has_children(node):

                  node = None
                  delete_self = True
            else:
                  node.is_end_word = False
                  delete_self = False
        else:

            child = node.children[self.get_index(key[level])]
            child_deleted = self.delete_helper(key,child,length,level+1)

            if child_deleted:
                node.children[self.get_index(key[level])] = None

                if self.has_children(node):
                    delete_self = False

                elif node.is_end_word:
                    delete_self = False

                else:
                    delete_self = True

            else:
                delete_self = False

        return delete_self

    def delete(self,key):

        if not self.root or not key:
              print('Key does not exist!')

        self.delete_helper(key,self.root,len(key),0)
        


# Input keys (use only 'a' through 'z' and lower case)
keys = ["the", "a", "there", "answer", "any", "by", "bye", "their", "abc"]
output = ["Not present in trie", "Present in trie"]

t = Trie()
print("Keys to insert: ")
print(keys)

# Construct Trie
for key in keys:
    t.insert(key)

# Search for different keys
if t.search("the") is True:
    print("the --- " + output[1])
else:
    print("the --- " + output[1])

if t.search("these") is True:
    print("these --- " + output[1])
else:
    print("these --- " + output[0])

if t.search("abc") is True:
    print("abc --- " + output[1])
else:
    print("abc --- " + output[1])

t.delete("abc")
print("Deleted key \"abc\"")

if t.search("abc") is True:
    print("abc --- " + output[1])
else:
    print("abc --- " + output[0])

#Function to get the number of words in the Trie
def count_words(node,count):
    if not node:
      return count
    
    if node.is_end_word:
        count = count+1

    for i in range(len(node.children)):

        if node.children[i]:
            count = count_words(node.children[i],count)

    return count    
keys = ["the", "a", "there", "answer", "any","by", "bye", "their", "abc"]
t = Trie()
print("Keys to insert: ")
print(keys)

# Construct Trie
for key in keys:
    t.insert(key)
    
count_words(t.root,0)
# Function to find words in a Trie
def find_words(node,curr,arr):
    
    if not node:
      return arr

    curr+=node.char
    if node.is_end_word:
      arr.append(curr)

    for i in range(len(node.children)):

        if node.children[i]:
            find_words(node.children[i],curr,arr)

    curr = curr[:-1]
    return arr
keys = ["the", "a", "there", "answer", "any","by", "bye", "their", "abc"]
t = Trie()
print("Keys to insert: ")
print(keys)

# Construct Trie
for key in keys:
    t.insert(key)

find_words(t.root,'',[])<jupyter_output>Keys to insert: 
['the', 'a', 'there', 'answer', 'any', 'by', 'bye', 'their', 'abc']
the inserted!
a inserted!
there inserted!
answer inserted!
any inserted!
by inserted!
bye inserted!
their inserted!
abc inserted!
{'fraction_non_alphanumeric': 0.1370345891165455, 'fraction_numerical': 0.003304692663582287, 'mean_word_length': 2.1074606433949348, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '606009', 'license': 'Unlicense', 'n_tokens_mistral': 1478, 'n_tokens_neox': 1432, 'n_words': 391, 'path': 'Trie.ipynb', 'repo_name': 'manashpratim/Algorithms-and-Data-Structures', 'size': '4539'}