Implement a trie

class Node:
  value = None
  final = None
  children = None

  def __init__(self, val, final):
    self.value = val
    self.final = final
    self.children = []

class Trie:
  def __init__(self):
    self.root = Node(None, True)

  def search(self, word):
    current_node = self.root
    i = 0

    while len(current_node.children) > 0 and i < len(word):
      found = False
      for child in current_node.children:
        if child.value == word[i]:
          if child.final and i == len(word) - 1:
            return True
          else:
            current_node = child
            i += 1
            found = True
            break
      if not found:
        break

    return False

  def insert(self, word):
    """ Returns true if the word was added and false if the word was
    already there """
    current_node = self.root
    i = 0

    cont = True
    while cont:
      cont = False
      for child in current_node.children:
        if child.value == word[i]:
          if child.final and i == len(word) - 1:
            return False
          else:
            current_node = child
            i += 1
            cont = True
            break

    inserted = False
    while i < len(word):
      if i == len(word) - 1:
        final = True
      else:
        final = False
      new_node = Node(word[i], final)
      current_node.children.append(new_node)
      current_node = new_node
      i += 1
      inserted = True

    return inserted


if __name__ == '__main__':
  trie = Trie()
  print "insert this, is new?", trie.insert("this")
  print "insert that, is new?", trie.insert("that")
  print "insert this, is new?", trie.insert("this")
  print "insert to, is new?", trie.insert("to")
  print "insert tone, is new?", trie.insert("tone")

  print "has this:", trie.search("this")
  print "has to:", trie.search("to")
  print "has tox:", trie.search("tox")
  print "has at:", trie.search("at")