Python - Get height of all children in Tree

Question

I'm having trouble visualizing a way to recursively get the height for all child nodes in a normal tree (non BST).

For BST's it's fairly obvious since there's only two nodes. How would you do it given the fact there could be multiple children per node?

How would you go about getting a list of all of the heights of child nodes in a normal tree?

I can't draw a picture since I have under 10 rep, but say I have a tree with multiple children. Each of those children leads to different leaf nodes at the end. I want a list of heights for each the paths from the root node to the leaf node. How would you go about doing this?

I know that:

def height(t):
    if not t.children:
        return 1
    else:
        return max(height(c) for c in t.children) + 1

Would obviously return the max height but I can't think of a way to do this for every path to the end of the tree recursively. I don't want just the maximum height, I want all of the heights.

huxley huxley · Accepted Answer · 2015-03-26T23:32:47

it's rather easy, you should pass another parameter, level which defined by 1 + the number of connections between the node and the root

when you get to a leaf you add the level value into a global list, at that point the level value will be the length of the path between the root to the leaf

at the end of the run the global list will contain all the heights

heights = []

def height(t, level=0):
    if not t.children:
        heights.append(level)
    else:
        for c in t.children:
            height(c, level+1)

Python - Get height of all children in Tree

1 Answers