trie.py

class Trie(object):
    def __init__(self,_key='',_val=None,_sub_nodes=None,_count=0):
        if not _sub_nodes:
            _sub_nodes = {}
        self._key = _key
        self._val = _val
        self._sub_nodes = _sub_nodes
        
        self._count = _count
        
        # _count does not take into account the _val itself
        if _val:
            self._count += 1          
        
    def __repr__(self,tab=0):
        _repr = ["%s'%s' => %s (count = %s)" % ("    "*tab, self._key, self._val, self._count)]
        for _,node in self._sub_nodes.iteritems():
            _repr.append(node.__repr__(tab+1))
        return "\n".join(_repr)
    
        
    
    def _split_self(self,split_index):
        """
        Split self._key at split_index, place self details into new sub node and 
        clear this node
        """
        new_sub_node = Trie(self._key[split_index:],self._val,self._sub_nodes)
        new_sub_node._count = self._count
        k_char = self._key[split_index]
        
        self._key = self._key[:split_index]
        self._val = None # this will be moved to sub_node
        self._sub_nodes = {}
        # self._count remains the smae during this operation

        self._sub_nodes[k_char] = new_sub_node
        
        
    def put(self,key,val): 
        """
        puts a new value in the trie at the specified key and returns True if successful
        
        if there is already a value in the trie for that key then new value is NOT inserted
        """
        
        # keys differ in the middle somewhere
        i = -1  # just in case the len(self._key) == 0 so that i is initialized
        for i in xrange(min(len(key),len(self._key))):
            if not key[i] == self._key[i]:
                self._split_self(i)
                self._sub_nodes[key[i]] = Trie(key[i:],val)
                self._count += 1
                return True
            
        i += 1
        
        # new key is shorter than self._key
        if len(key) < len(self._key):
            self._split_self(i)
            self._val = val
            self._count += 1
            return True
        
        # self._key is shorter than new key
        if len(self._key) < len(key):
            sub_node = self._sub_nodes.get(key[i])
            if sub_node: # sub_node already exists
                success = sub_node.put(key[i:],val)
                self._count += success
                return success
            else: # making sub_node
                self._sub_nodes[key[i]] = Trie(key[i:],val)
                self._count += 1
                return True
            
        # keys are same don't add it
        return False

trie = Trie()

trie.put('abcdefghi1klmnopqrstuvwxyz',1)
trie.put('abcdefghijklmnopqrs2uvwxyz',2)
trie.put('abcd3fghijklmnopqrstuvwxyz',3)
trie.put('abcdefghijklmn4pqrstuvwxyz',4)
trie.put('abcdefghijk5mnopqrstuvwxyz',5)
trie.put('abcdefghijklmnopqrstuv6xyz',6)

print trie

prints

'' => None (count = 6)
    'abcd' => None (count = 6)
        '3fghijklmnopqrstuvwxyz' => 3 (count = 1)
        'efghi' => None (count = 5)
            '1klmnopqrstuvwxyz' => 1 (count = 1)
            'jk' => None (count = 4)
                '5mnopqrstuvwxyz' => 5 (count = 1)
                'lmn' => None (count = 3)
                    '4pqrstuvwxyz' => 4 (count = 1)
                    'opqrs' => None (count = 2)
                        '2uvwxyz' => 2 (count = 1)
                        'tuv6xyz' => 6 (count = 1)

It keeps track of the counts for each branch of the Trie too so you know if it's worth digging deeper.