code: def insert_trie(trie, value):  # aka get_subtrie_or_insert
      
      if value in trie:
          return trie[value]
      multi_check = False
      for key in tuple(trie.keys()):
          if len(value) > len(key) and value.startswith(key):
              return insert_trie(trie[key], value)
          elif key.startswith(value):  # we know the value is not in the trie
              if not multi_check:
                  trie[value] = {}
                  multi_check = True  # there can be multiple longer existing prefixes
              dict_ = trie.pop(key)  # does not break strie since key<->dict_ remains unchanged
              trie[value][key] = dict_
      if value not in trie:
          trie[value] = {}
      return trie[value]
docs: Insert a value into the trie if it is not already contained in the trie.
          Return the subtree for the value regardless of whether it is a new value
          or not.