CODEWITHSUNDEEP
pythonpython-3.xtreeheight
CoolKid
CoolKid

Reputation: 143

How to find height for non-binary tree?

So I am struggling with writing a recursive method for finding height for a tree. This each tree node has a list of children. My code returns exception because max somehow is an empty sequence. Could someone provide a valid one? 

def height(t):
    """
    Return 1 + length of longest path of t.

    @param Tree t: tree to find height of
    @rtype: int

    >>> t = Tree(13)
    >>> height(t)
    1
    >>> t = descendants_from_list(Tree(13), [0, 1, 3, 5, 7, 9, 11, 13], 3)
    >>> height(t)
    3
    """
    # 1 more edge than the maximum height of a child, except
    # what do we do if there are no children?
    if t.children is None:
        return 1

    else:
        return 1+max(height(x) for x in t.children)

Upvotes: 1

Views: 1820

Answers (1)

Antti Haapala -- Слава Україні
Antti Haapala -- Слава Україні

Reputation: 133879

I guess the t.children is an empty list - [] - on leaf nodes, not None. 

>>> [] is None
False
>>> not []
True

max cannot be used with empty iterables - what do you imagine would be the maximum value in [], 0 or -∞, or 42?

Just test with if not t.children::

if not t.children:
    return 1

else:
    return 1 + max(height(x) for x in t.children)

Upvotes: 5

Related Questions