Uncategorized

How to is my prefix tree (trie) creating cycles? Python



When I create a prefix tree from a list of strings, cycles are being created. The cycle is that the root will have a pointer to a child, and the child will also have a pointer to itself.

Can anyone spot what I did wrong?

class TreeNode:
    def __init__(self, value="", children=dict()):
        self.value = value
        self.children = children

def convert_list_to_prefix_tree_nodes(words: list[str]):
    root = TreeNode()

    for word in words:
        itr = root
        i = 0
        while i < len(word):
            char = word[i]
            if char not in itr.children:
                itr.children[char] = TreeNode(char)                
            itr = itr.children[char]
            i += 1
        # Terminating node showing this is an end to a word, even if another continues.
        itr.children['*'] = TreeNode('*')
    
    return root

I have traced through and everything works fine.

I would like the result to be a prefix tree without cycles.



Source link

Leave a Reply

Your email address will not be published. Required fields are marked *