Search using Trie Data Structure

Trie.py

class TrieNode:
  def __init__(self, value):
    self.value = value;
    self.children = {}
    self.is_end = False

  def __str__(self):
    txt = ""
    for key in self.children:
      value = self.children[key]
      txt += key + "[" + str(value) + "]"
  
    return txt
    
    
class Trie:
  def __init__(self):
    self.root = TrieNode("");
  def insert(self, text):
    node = self.root
    for char in text:
      if char in node.children:
        node = node.children[char];
      else:
        newNode = TrieNode(char)
        node.children[char] = newNode
        node = newNode
    node.is_end = True
    
  def transverse(self, node, previous):

    if node.is_end:
      self.output.append(previous)
    try:
      for char in node.children:
        newNode = node.children[char]
        self.transverse(newNode, previous + char)
    except Exception as eee:
      print("here",previous, node.children)
      
    
      
    
  def query(self, query):
    self.output = []
    node = self.root
    for char in query:
      if char in node.children:
        node = node.children[char];
      else:
        break
    self.transverse(node, query);

    return self.output
    
  def __str__(self):
    return str(self.root)



trie = Trie()
trie.insert("woman")
trie.insert("worm")
trie.insert("word")
trie.insert("weed")
trie.insert("wedding")
print(trie.query("wed"))


# Adapted from https://albertauyeung.github.io/2020/06/15/python-trie.html/