pythonpointersdata-structurestrie

why the pointer is not incrementing at line 27


i am implementing the trie data structure, why my pointer is not incrementing at line# 27. all the characters are getting into forst node only. this is my code

class Trienode:
    data:str
    next:list = [None]*26
    isTerminal:bool = False

    def __init__(self,data):
        self.data = data


class Trie:

    def __init__(self):
        self.root  = Trienode('#')

    def insert(self,data):
        
        temp = self.root

        for ch in data:
            index = ord(ch)- ord('a')
            # print(temp.next[index])
            if temp.next[index]==None:
               
                temp.next[index] = Trienode(ch)
                temp = temp.next[index]
            
            else:
                temp = temp.next[index]
        temp.isTerminal = True

    def display(self):
        temp = self.root
        for i in range(26):
            print(temp.next[i])


if  __name__=='__main__':
    root = Trie()
    root.insert("apple")
    root.insert("pineapple")

    root.display()

This is the output on console i am printing the pointer array of first node console output

i tried the same logic to increment pointer in Linkedlist it is working fine.


Solution

  • I've modified your sample a little bit. Relevant changes are highlighted with a comment

    class Trienode:
        def __init__(self, data):
            self.data: str = data
            self.next: list = [None] * 26
            self.isTerminal: bool = False
    
        def __str__(self):  # get more info on display
            return f"{self.data} - {''.join(str(n) for n in self.next if n is not None)}"
    
        def __repr__(self):  # appears nicely in my IDE ;)
            return f'Trienode({self.data})'
    
    
    class Trie:
    
        def __init__(self):
            self.root = Trienode('#')
    
        def insert(self, data):
    
            temp = self.root
    
            for ch in data:
                index = ord(ch) - ord('a')
                if temp.next[index] is None:  # error was there I guess
                    temp.next[index] = Trienode(ch)
                temp = temp.next[index]  # and here also
            temp.isTerminal = True
    
        def display(self):
            self._display(self.root)
    
        def _display(self, node):  # must use a recursion to display all the children
            print(node)
            for child in node.next:
                if child is not None:
                    self._display(child)
    
    
    
    if __name__ == '__main__':
        root = Trie()
        root.insert("apple")
        root.insert("pineapple")
    
        root.display
    

    Hope this helps