title: Python spell checker using a trie
body: <p>I am trying to implement a spell checker using a trie data structure. I currently have the following outline for a <code>Node</code>:</p>
  
  <pre><code>class Node:
      def __init__(self):
          self.next = {}
          self.word_marker = False
  
      def add_item(self, string):
          #if the length of the string is 0 then return. When the end of the word 
          #comes set the word_marker to true
          if len(string) == 0:
              self.word_marker = True
              return
          #set the key to the first letter of the string and reformat the string to reflect the first letter taken out
          #ultimately going to store the letters for each node as the key
          key = string[0]
          string = string[1:]
  
          #if there is a key in the dictionary, then recursively call add_item with new string
          if key in self.next:
              self.next[key].add_item(string)
  
          else:
              node = Node()
              self.next[key] = node
              node.add_item(string)
  </code></pre>
  
  <p>The next thing that I want to do is write the function to search for a <code>string</code> and then return a suggested spelling. (<code>def correct(self, string)</code>). How would I go through this trie to implement the search? Assume that I already added a list of words to the trie by defining a root node <code>root</code>, then using <code>add_item</code> for each of the words in the list.</p>