I made this trie

class Trie:
    def __init__(self):
        self.root = {}
        self.end = '\0'

    def add(self,text):
        node = self.root 
        for letter in text:
            if letter in node:
                node = node[letter]
            else:
                node[letter]={}
                node = node[letter]
        node[self.end] = True
        
        
    def addAll(self,lst):
        for word in lst:
            self.add(word)

And made this function to print all the words in the trie

# takes in trie.root
def printWords(root,word=""):
    if root==True:
        print(word[:-1])
        return

    for letter in root:
        printWords(root[letter],word letter)

How can I find the big O of this function printWords.

CodePudding user response：

The worst time complexity is O(