Convert words into a searchable n-ary tree

treenode.py

class Node():
    def __init__(self):
        # Note that using dictionary for children (as in this implementation) would not allow lexicographic sorting mentioned in the next section (Sorting),
        # because ordinary dictionary would not preserve the order of the keys
        self.children = {}  # mapping from character ==> Node
        self.parent = None
        self.name = ""
        self.value = -1
       
    def __str__(self):
        return "Value: %s Children:%s"%(str(self.value), str(self.children.keys()))
        
def find(node, key):
    for char in key:
        if node.value > -1:
            break
        if char in node.children:
            node = node.children[char]
        else:
            return None
    return node.value

def get_size(obj, seen=None):
    """Recursively finds size of objects"""
    size = sys.getsizeof(obj)
    if seen is None:
        seen = set()
    obj_id = id(obj)
    if obj_id in seen:
        return 0
    # Important mark as seen *before* entering recursion to gracefully handle
    # self-referential objects
    seen.add(obj_id)
    if isinstance(obj, dict):
        size += sum([get_size(v, seen) for v in obj.values()])
        size += sum([get_size(k, seen) for k in obj.keys()])
    elif hasattr(obj, '__dict__'):
        size += get_size(obj.__dict__, seen)
    elif hasattr(obj, '__iter__') and not isinstance(obj, (str, bytes, bytearray)):
        size += sum([get_size(i, seen) for i in obj])
    return size
    
def insert(root, string, value):
    node = root
    index_last_char = None
    for index_char, char in enumerate(string):
        if char in node.children:
            #value is no longer unique at this level
            node.value=-1
            node = node.children[char]
        else:
            index_last_char = index_char
            break

    # append new nodes for the remaining characters, if any
    if not index_last_char is None: 
        node.value=-1
        for char in string[index_last_char:]:
            node.children[char] = Node()
            node.children[char].parent = node
            node.children[char].name = char
            #store value in all nodes down the tree
            node.children[char].value = value
            node = node.children[char]
    # return terminal node
    return node

def dumpTreeHash(node,parent="",noParents=True,spacing=0,CR=""):
    if noParents:
        ret="{'v':%d,'c':{"%(node.value)
    else:
        ret="{'pa':'%s','val':%d,'nm':'%s','ch':{"%(parent,node.value,node.name)
    if node.children:
        for aa in node.children:
            ret = ret+"%s%s'%s':%s,"%(CR," "*spacing,aa,dumpTreeHash(node.children[aa],parent+node.name,noParents,spacing + 4 if spacing>0 else 0,CR))
        ret=ret[:-1]
    ret=ret+"}}"
    return ret

def dumpTreeTuple(node,parent="",noParents=True):
    if noParents:
        ret="('%s',%d,("%(node.name,node.value)
    else:
        ret="('%s',%d,'%s',("%(node.name,node.value,parent)
    if node.children:
        for aa in node.children:
            ret = ret+"%s,"%(dumpTreeTuple(node.children[aa],parent+node.name,noParents))
        ret=ret[:-1]
    ret=ret+"))"
    return ret

def testNodes(top,words):
    reverse=[]
    for idx,ww in enumerate(words):
       reverse.append(insert(top,ww[0],idx))
    return reverse
 
def walkUpTree(node):
    soFar=""
    while not node.parent is None:
        soFar=node.name+soFar
        node=node.parent
    return soFar
 
def delTree(node,soFar=""):
    myKids=node.children.keys()
    for char in myKids:
        print "DEL \"%s\" %s"%(soFar+char,str(node.children[char]))
        delTree(node.children[char],soFar+char)
        del node.children[char]

def walkDownTree(node,soFar=""):
    for char in node.children:
        print "N: \"%s\" %s"%(soFar+char,str(node.children[char]))
        walkDownTree(node.children[char],soFar+char)
    
if __name__=="__main__":
    top=Node()
    top.name=""
#    rev=testNodes(top)