CODEWITHSUNDEEP
pythonrecursiontree
Ibrahim Abouhashish
Ibrahim Abouhashish

Reputation: 45

Maximum sum in a non-binary tree in Python

I have a non-binary tree and each node of that tree has a value. I would like to get the maximum sum available. For example:

              10
       9       8      7
    1  2  5     5      15

The return would be 10+7+15=32 I know how to do this if the tree was binary, but what if the tree has n branches? This code is the binary one taken from the first answer of this question: Find the maximum sum of a tree in python

Upvotes: 0

Views: 1905

Answers (2)

John Gordon
John Gordon

Reputation: 33275

Assuming each node has a value attribute and a children attribute which is either a list of child nodes, an empty list, or None:

def tree_sum(node):
    if node.children:
        child_sums = []
        for child in node.children:
            child_sums.append(tree_sum(child) + node.value)
        return max(child_sums)
    else:
        return node.value

print tree_sum(root)

Upvotes: 3

fips
fips

Reputation: 4379

Here's one approach:

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []


def max_sum(root):
    if len(root.children) == 0:
        return root.value

    sums = []
    for child in root.children:
        sums.append(root.value + max_sum(child))

    return max(sums)


n_9 = Node(9)
n_9.children.extend([Node(1), Node(2), Node(5)])

n_8 = Node(8)
n_8.children.extend([Node(5)])

n_7 = Node(7)
n_7.children.extend([Node(15)])

n_10 = Node(10)
n_10.children = [n_9, n_8, n_7]

print max_sum(n_10)
# Output: 32

Upvotes: 0

Related Questions