Find the maximum sum of a tree in python

Question

I have a tree of numbers that I want to be able to find the sum of numbers. Below each number are two children to the left and right Of all the possible paths, I want to be able to find the biggest number through all the possible paths. Here is an example

       8
   3      11
10   2  32  6

returns 8+11+32=51

I feel that this is a recursion problem but I am stuck with my code and keep getting errors. I think that I am approaching this incorrectly. Below is my code:

# Returns root key value
def getRootValue(root):
    return root

# Returns reference to left child
def getLeftChild(root):
    value=None
    if root.leftChild!=None:
        value=root.leftChild
    return value

# Returns reference to right child
def getRightChild(root):
    value=None
    if root.rightChild!=None:
        value = root.rightChild
    return value

def sum_of_branch(root):
    sum=0  
if root.getLeftChild() ==None and root.getRightChild()==None:
    return rounds
else:
    rounds+=rounds+1
    keys_sum[depth]=sum+root.key
    return sum_to_deepest(root.left), sum_to_deepest(root.right)
    if root.getLeftChild()!=None:
        rounds+=root.getLeftChild().branchLenSum()
    if root.getRightChild()!=None:
        rounds+=root.getRightChild().branchLenSum()
    return rounds

can you include the full code ? including the structure of each node and also sum_to_deepest function — g4ur4v
– g4ur4v, Commented Sep 20, 2014 at 21:50

Jose Varez · Accepted Answer · 2014-09-20 22:04:48Z

2

Without knowing the data structure you are using is difficult to give you an answer. But I think you are looking for somenthing like this:

def sum_of_branch(root):
    # If it has not childs we have arrived at the end of the tree.
    # We return the value of this child.
    if root.getLeftChild() ==None and root.getRightChild()==None:
        return getRootValue(root)
    else:
        # If it has children we calculate the sum of each branch. 
        leftSum = sum_of_branch(root.getLeftChild())
        rightSum = sum_of_branch(root.getRightChild())
        # And return the maximun of them.
        if leftSum > rightSum:
            return getRootValue(root) + leftSum
        else:
            return getRootValue(root) + rightSum

edited Sep 20, 2014 at 22:04

answered Sep 20, 2014 at 21:58

Jose Varez

2,0771 gold badge14 silver badges9 bronze badges

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

Collectives™ on Stack Overflow

Find the maximum sum of a tree in python

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related