How to find height for non-binary tree?

Question

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)

Fix your indentation please : )

Torxed
– Torxed

2016-03-10 15:37:17 +00:00
Commented Mar 10, 2016 at 15:37 — Torxed
– Torxed, Commented Mar 10, 2016 at 15:37

Antti Haapala · Accepted Answer · 2016-03-10 15:38:10Z

5

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)

answered Mar 10, 2016 at 15:38

Antti Haapala

135k23 gold badges297 silver badges349 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Russell Richie Over a year ago

+1 This helped me figure out how to compute the parse tree height of a spaCy dependency parse. (Commenting here so people can maybe find this q/a by searching those terms.

Collectives™ on Stack Overflow

How to find height for non-binary tree?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related