'''
This is an Example Program to illustrate Insertion and Searching Concept over Trie Data Structure in Python
'''
class TrieNode:
    def __init__(self):
        self.children = [None]*26
        # isEndOfWord is True if node represent the end of the word thats a LEAF NODE
        self.isEndOfWord = False

class Trie:
    def __init__(self):
        self.root = self.getNode()

    def getNode(self):
        return TrieNode()

    def _charToIndex(self,ch):
        # use only 'a' through 'z' and lower case
        return ord(ch)-ord('a')

    def insert(self,key):
        pointr = self.root
        length = len(key)
        for level in range(length):
            index = self._charToIndex(key[level])
            if not pointr.children[index]:
                pointr.children[index] = self.getNode()
            pointr = pointr.children[index]
        pointr.isEndOfWord = True

    def search(self, key):
        pointr = self.root
        length = len(key)
        for level in range(length):
            index = self._charToIndex(key[level])
            if not pointr.children[index]:
                return False
            pointr = pointr.children[index]

        return pointr != None and pointr.isEndOfWord

# driver function
def main():

    # Inputing keys using only 'a' through 'z' and lower case can be any length stirings since Structure is Dynamic
    keys = ["there","is","an","anaswer","in","some",
            "ones","mind","dhanush"]
    output = ["Not present in trie",
              "Present in tire"]
    # Trie object
    t = Trie()
    # Construct trie
    for key in keys:
        t.insert(key)

    # Search for different key elements in the Trie
    print("{} ---- {}".format("the",output[t.search("the")]))
    print("{} ---- {}".format("these",output[t.search("these")]))
    print("{} ---- {}".format("mind",output[t.search("mind")]))
    print("{} ---- {}".format("dhanush",output[t.search("dhanush")]))

if __name__ == '__main__':
    main()
  '''
  Trie is a concept where in the Strings are stored in the tree Structure in which each node holds a single character.
  Trie is very Useful in word prediction Concept and Word Correction Methods.
  Trie's main concept is to store the values in the form of tree into which we insert strings as a whole input and branch them to traverse in am easy manner.
 -DhanushKJ
  '''