Please help me to solve the issue in trie data structure getting the all words with prefix

https://forum.freecodecamp.org/t/please-help-in-trie-fix-issue/572090

What is the issue? And what challenge is this?

please help me in this trie data structure getting the all words with prefix are not correct

I can’t read code when it is inside an image.
Please post actual code if you need to get someone to read it.
Also please clarify what it is you need help with. I’m still not understanding.


Key = TypeVar("Key")

@dataclass
class TrieNode(Generic[Key]):
    key: Optional[Key]
    parent: Optional[TrieNode]
    children: dict[Key, TrieNode] = field(init=False, default_factory=dict)
    is_terminating: bool = field(init=False, default=False)




class Trie(Generic[Key]):
    def __init__(self):
        self.root = TrieNode(key=None, parent=None)

    def insert(self, collection: str) -> None:
        current = self.root
        for element in collection:
            if element not in current.children:
                current.children[element] = TrieNode(key=element, parent=current)
            current = current.children[element]
        current.is_terminating = True

    # Support the "in" operator
    def __contains__(self, collection: str) -> bool:
        return self.contains(collection)

    def contains(self, collection: str) -> bool:
        current = self.root
        for element in collection:
            child = current.children.get(element, None)
            if not child:
                return False
            current = child
        return current.is_terminating

    def remove(self, collection: str) -> None:
        current = self.root
        for element in collection:
            child = current.children.get(element, None)
            if not child:
                return
            current = child
        if not current.is_terminating:
            return
        current.is_terminating = False

        while current.parent and not current.children and not current.is_terminating:
            parent = current.parent
            parent.children.pop(current.key)
            current = parent

    def collections_starting_with_prefix(self, prefix: str) -> list[str]:
        current = self.root
        for element in prefix:
            child = current.children.get(element, None)
            if not child:
                return []
            current = child
        return self.collections_starting_with_prefix_after_node(prefix, current)

    def collections_starting_with_prefix_after_node(
        self, prefix: str, node: TrieNode
    ) -> list[str]:
        # 1
        results: list[str] = []

        results.append(prefix)

        # 2
        for child in node.children.values():
            if child.key:
                prefix += child.key
            results.extend(
                self.collections_starting_with_prefix_after_node(prefix, child)
            )

        return results


if __name__ == "__main__":
    trie = Trie()
    trie.insert("cat")
    trie.insert("car")
    trie.insert("card")
    trie.insert("care")
    trie.insert("cared")
    print(trie.collections_starting_with_prefix("car"))

when I search words with perfix this shows wrong words
correct result is [“car”, “card”,“care”, “cared”].
but it shows wrong result [“car”,“card”,“carde”,“carded”]

First of all, you need to first explain what task your code is trying to accomplish. What is the problem this code is trying to solve?

I want words of a string with help of the collection_start_with_prefix method but when run the code it fetches the wrong words which I did not insert in the trie
it shows the [‘car’, ’ card’, ‘carde’, ‘carded’] but the correct one is [‘car’, ‘card’, ‘care’, ‘cared’] with a prefix search, I want to know why this code fetches the wrong string of words.

def collections_starting_with_prefix(self, prefix: str)

this method is not show correct result

Please reply to me if you check my code

Please help me. My code is trying to accomplish search all strings of words with prefix matching but it shows the wrong result with ‘car’ prefix search. the correct result is [“car”, “card”, “care”, “cared”].
but it shows the wrong result [“car”,“card”,“carde”, “carded”]

I still don’t understand you.
You said you are trying to find words that start with ‘car’
All these words that you said are wrong all start with car.

I inserted only these words then it should be show these words [‘car’, ‘card’, ‘care’, ‘cared’] with car prefix

trie.insert(“cat”)
trie.insert(“car”)
trie.insert(“card”)
trie.insert(“care”)
trie.insert(“cared”)
but shows [‘car’, ‘card’, ‘carde’ , ‘carded’]
why this shows ‘carde’ and ‘carded’ which I did not inserted in trie.

only two words are wrong which I did not insert in trie ‘carde’, and ‘carded’

can you provide a working version of your code in replit?

this is my working code repl linkhttps://replit.com/@murtaza63/Trie-Data-structure#main.py

1 Like

So I played with the code a bit to try to understand what was happening.

I removed the inserts and used exactly 2
cat
car

I noticed that the structure you were creating essentially makes this type of tree
c at the top
a below that
t & r children of a together

Then I modified the prefix to be a simple ‘c’ and searched for that
and I got the result
[‘cat’,‘catr’]

The reason seems to be the function
collections_starting_with_prefix_after_node

This part of the code finds all the children and appends them to the prefix
so you end up with catr because t and r are both children of a

So try to figure out what you should be doing instead of just blindly adding all the children to the prefix

Thanks for your reply and help me but I am confused about that what should be changed in this code for child in node.children.values(): if child.key: prefix += child.key
so it can work properly.

you are adding all the children so that is giving you the wrong result
you have to find a way to split the children up into different words I guess
so that instead of getting
[“cat”,“catr”]
you get
[“cat”,“car”]

First thing would be to stop blindly adding all the children to the prefix I would guess.
Perhaps you have to check if the child is the terminating node and if it is, you have to somehow reset so that the next child gets added to a different prefix?
Not sure really.

Thanks so much with the help of your advice issue is solved

1 Like