How to search for a word in a tree represented as a dictionary of dictionaries in python?

I have a dictionary of words like this -

{"a": {"b": {"e": {},
             "f": {},
             "g": {"l": {},
                   "m": {},
                   "n": {}}},
       "c": {"h": {},
             "i": {}},
       "d": {"j": {},
             "k": {}}}}

It's a tree like structure that translates like this

            a   
          /  |\
         /   | \
        /    |  \
       /     |   \
      /      |    \
     /       |     \
    b        c      d
  / | \      | \    |\
e   f  g     h  i   j k
      / |\  
     l  m n

And I have a list of characters - [a, c, h, q, r] I want to find if the given word(the list of characters) exist in the dictionary and if it doesn't, return the longest sub-sequence from the beginning that exists. If it does, return the same list.

In the above example, the return should be - [a, c, h]

Solution

edit - thank you for updating the data to something that makes sense.

Traversing a trie is pretty interesting. Here is a quick demonstration.

trie = {"a": {"b": {"e": {},
                    "f": {},
                    "g": {"l": {},
                          "m": {},
                          "n": {}}},
              "c": {"h": {},
                    "i": {}},
              "d": {"j": {},
                    "k": {}}}}

target = 'achqr'
sub_trie = trie
longest_sequence = []
for c in target:
    sub_trie = sub_trie.get(c)
    if sub_trie is None:  # the letter being looked for doesn't exist after this sequence
        break
    longest_sequence.append(c)  # track the sequence since the trie is not reverse linked
print(longest_sequence)