Python 3 Trie Prefix Searching with Recursive Printing

trie.py

# https://albertauyeung.github.io/2020/06/15/python-trie.html
# Mainly this but I added some neat features and simplified some parts

class Trie:
    class Node:
        def __init__(self, char):
            self.char = char
            self.children = {}
            # If true it marks the end of a string
            # If this isn't here, then we couldn't have overlapping nodes like "change" and "cha"
            self.isWord = False 
        
        def __repr__(self):
            # Recursively outputs a str so you can see the entire structure when printing
            if self.children:
                return str(self.children)
            else:
                return '\'' + self.char + '\''

    def __init__(self, words):
        # Takes an array of words and populates the trie
        self.root = Trie.Node("")    
        for word in words:
            self.insert(word)

    def dfs(self, node, prefix, output):
        # Go through the subtree of node, add prefix to the output, and populate an array output
        if node.isWord: 
            output.append(prefix)
        for children in node.children.values():
            self.dfs(children, prefix+children.char, output)

    def searchPrefix(self, prefix):
        # Given a prefix str, return all of the strings in the tree that has it as it's prefix
        node = self.root
        for c in prefix:
            if c in node.children:
                node = node.children[c]
            else:
                return []
        output = []
        self.dfs(node, prefix, output)
        return output

    def insert(self, word):
        # Insert word into the trie tree
        node = self.root
        for c in word:
            # This is a pretty slick trick if I say so myself
            # Creates Node(c) if it is missing then assigns that new Node to node to traverse
            # If it exists, then set it to node to traverse
            node = node.children.setdefault(c, Trie.Node(c))
        node.isWord = True
    
    def __repr__(self):
        return str(self.root)

words = ['dog', 'dogs', 'dodges', 'door', 'insert', 'cat', 'cats', 'catsdogs', 'dogscats']
trie = Trie(words)
print(trie)
output = []
trie.dfs(trie.root, "", output)
print(output)
print(trie.searchPrefix('do'))
print(trie.searchPrefix('ca'))

"""
{'d': {'o': {'g': {'s': {'c': {'a': {'t': {'s': 's'}}}}}, 'd': {'g': {'e': {'s': 's'}}}, 'o': {'r': 'r'}}}, 'i': {'n': {'s': {'e': {'r': {'t': 't'}}}}}, 'c': {'a': {'t': {'s': {'d': {'o': {'g': {'s': 's'}}}}}}}}
['dog', 'dogs', 'dogscats', 'dodges', 'door', 'insert', 'cat', 'cats', 'catsdogs']
['dog', 'dogs', 'dogscats', 'dodges', 'door']
['cat', 'cats', 'catsdogs']
"""

Note you can implement a trie without any classes doing this:

trie = {}
for word in words:
    node = trie
    for char in word:
        node = node.setdefault(char, {})
    node['end'] = word