CODEWITHSUNDEEP
pythonfunctionbinary-tree
colalove
colalove

Reputation: 31

How to define a function that calculate the sum of all leaves in a binary number tree in python?

Just like ((1,(2,3)),4)

how can I get the sum of all the leaves through a defined function? like 1+2+3+4?

My function is like following but still getting an error and I just confused and no idea with this.

def add_leaves(tree):
    """returns to the sum of all the numbers in the binary-number-tree
    bin -> int"""
    if not isinstance(tree,tuple):
        return tree[0] + tree[1]
    else:
        return add_leaves(tree[0]) + add_leaves(tree[1])

Upvotes: 0

Views: 1181

Answers (2)

Cory Kramer
Cory Kramer

Reputation: 117856

Here is a recursive solution that will do this for any n-ary tree (instead of just a binary tree). This will also work for arbitrary leaves, instead of just full trees.

def add_leaves(x):
    if isinstance(x, int):
        return x
    else:
        return sum(add_leaves(i) for i in x)

>>> tree = ((1,(2,3)),4)
>>> add_leaves(tree)
10

Upvotes: 2

Blckknght
Blckknght

Reputation: 104682

The code you're using for your base case is wrong. The isinstance call will be False when the function is passed a leaf value (an int), but you're still trying to index that value. You should just return the tree in that case:

def add_leaves(tree):
    """returns to the sum of all the numbers in the binary-number-tree
    bin -> int"""
    if not isinstance(tree,tuple):
        return tree                                         # fix is here!
    else:
        return add_leaves(tree[0]) + add_leaves(tree[1])

Upvotes: 2

Related Questions