n_arry_tree.py

def max_depth(map, depth=0):
    """return's the max depth of a n-arry tree"""
    if isinstance(map, dict):
        depth += 1
        val = 0
        for x in map.itervalues():
            val = max(val, max_depth(x, depth))
        return val
    else:
        return depth


def balance_tree(map, depth):
    """Puts space and makes all the nodes of same depth"""
    result = {}
    if isinstance(map, dict):
        for k, v in map.items():
            result[k] = balance_tree(v, depth - 1)
    else:
        if depth:
            result[" "] = balance_tree(" ", depth - 1)
        else:
            return " "
    return result


def propogate_heights(map):
    result = {}
    sum = 0
    if isinstance(map, dict):
        for k in sorted(map.iterkeys()):
            v = map[k]
            child_val = span_tree(v)
            sum += child_val[0]
            result[k] = child_val
    else:
        return 1, None
    return sum, result

def tree_to_html(tree):
    result = "<thead><tr>"
    queue = deque()
    temp = []
    for k in sorted(tree.iterkeys()):
        v = tree[k]
        result += '<th colspan="%d">%s</th>' % (v[0], k)
        temp.append(v[1])
    result += "</tr>"
    queue.append(temp)
    while len(queue) > 0:
        level = queue.popleft()
        temp = []
        if level[0]:
            result += "<tr>\n"
        for l in level:
            if l:
                for k in sorted(l.iterkeys()):
                    v = l[k]
                    result += '<th colspan="%d">%s</th>\n' % (v[0], k )
                    temp.append(v[1])
        if level[0]:
            queue.append(temp)
            result += "\n</tr>"
    result += "</thead>"
    return result