title: Time complexity of Search operation in TRIE data structure
body: <p>I am trying to implement a dictionary based trie data structure. Please find the python code below.</p>
  
  <pre><code>class Trie:
    def __init__(self):
       self.word_end = '_end_'
       self.root = {}
  
    def add_word(self, word):
       self.add_words([word])
  
    def add_words(self, words):
       for word in words:
           current_dict = self.root
           for letter in word:
               current_dict = current_dict.setdefault(letter, {})
           current_dict[self.word_end] = self.word_end
  
  
    def check_word(self, word):
       current_dict = self.root
       for letter in word:
           if letter in current_dict:
               current_dict = current_dict[letter]
           else:
               return False
       else:
           if self.word_end in current_dict:
               return True
           else:
               return False
  
  
  
  tree = Trie()
  tree.add_words(['foo', 'bar', 'baz', 'barz'])
  print tree
  """
  {'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}}, 
               'z': {'_end_': '_end_'}}}, 
   'f': {'o': {'o': {'_end_': '_end_'}}}}
   """
  
  print check_word('baz')
  # True
  print check_word('barz')
  # True
  print check_worf('barzz')
  # False
  </code></pre>
  
  <p>I see the complexity of searching a word is O(m) where m is the length of the word being searched. Also, adding a word has very similar complexity - O(m) where m is the length of the word being added.</p>
  
  <p><strong>Question:</strong>
  These complexities are too good. Can someone confirm these complexities? Is there something wrong in my implementation of Trie?</p>