Nested Dictionary Access and value Return

Question

I have a number of nested dictionaries where the key is a character i.e: "D" and the value is a reference to an object containing another dictionary.

EX:

For the words "DAD", "BAD", "DADDY":

          B|D
         /  \
       A     A
      /       \
     D         D
    /          /\
   *          *  D
                  \
                   Y
                    \
                     *

If we are accessing "BAD"
    self.child = { B : ref to object, D : ref to object}
    self.child.get("B").child = { A : ref to object }
    self.child.get("B").child.get("A").child = { D : {}}

I am trying to access the tree and print all the words out of the tree, either the full tree, or just the portions that match the inputted character. ie: if I input "B" I want "BAD", if I input "D" I want "DAD", "DADDY"

Right now the below code does not return as expected, if "D" is inputted, "DAD" and "DY" are returned.

Self values are initialized earlier in the class.

def traverseTree(self, dictionary, baseValue):
    for key, value in dictionary.items():
        if isinstance(value.child, dict):
            if not value.leaf:
                self.accum += key
            else:
                self.l.append(baseValue + (self.accum + key)
                self.accum = ''
            self.traverseTree(value.child, baseValue)

I am suspecting that the first chunk of "DADDY" (DAD) are chopped off because their values are not pushed into the accumulator. I believe that with this recursive algo I am visiting each node, since I reach the terminal points, but what is the best practice to recursively access, and store all the word values?

MRE:

class Trie:
    def __init__(self):
        self.dict = {}
        self.terminate = False

    def insert(self, word):
        if len(word) == 0:
            self.terminate = True
        else:
            if word[0] in self.dict:
                self.dict[word[0]].insert(word[1:])
            else:
                self.dict[word[0]] = Trie()
                self.dict[word[0]].insert(word[1:])

    def terminal(self):
        if self.terminate:
            return True

    def autoSearch(self, toSearch):
        if toSearch == '':
            return self.traverseTreeTest()

    def traverseTreeTest(self):
        if self.terminate:
            return [""]
        returnval = []
        for key, children in self.dict.items():
            returnval.extend([key + rest for rest in children.traverseTreeTest()])
        return returnval

word = ["D","DAD", "B", "BAD", "DADDY", "Lad"]
x = Trie()
for y in word:
    x.insert(y)
print(x.autoSearch(''))

Answer 1

I think the problem is that at every level you're updating self.l and self.accum, which modifies the nested objects, so you don't get the full result in the top-level object.

Here's a version that just returns everything as a list, rather than modifying the objects.

def traverseTree(self):
    if self.leaf:
        return [""]

    returnval = []
    for key, value in self.child.items():
        returnval.extend([key + rest for rest in value.traverseTree()])
    return returnval

This is basic recursion. All cases return a list of strings. The base case is a leaf, which returns a list with just an empty string in it.

The recursive case loops over the dictionary, prefixing the key to the result of recursing into the child, and returning a list of all those strings.