CODEWITHSUNDEEP
python-3.xbinary-tree
pharaphoks
pharaphoks

Reputation: 51

How to calculate sum of tree branches using Python?

I am currently practicing python and I am having an issue with binary tree. I think I am fairly good in python but I am having a hard time with binary trees.

The problem is: Problem

The first line of the function definition is given so I need to use it as is, however not sure how to calculate sum of branches.

def solution(arr):
    root = arr[0]

   for i in arr.index(i):
       left = sum(arr[i]-arr[0])
       right = sum(arr[i+1]-arr[0])

   if left > right:
       return "Left"

   elif left < right:
        return "Right"

   else:
       return ""

The error I get is 

 Traceback (most recent call last):
  File "/usercode/file.py", line 36, in <module>
    test()
  File "/usercode/file.py", line 34, in test
    json.dumps(solution(*input), separators=(',', ':')))
  File "/usercode/file.py", line 5, in solution
    for i in arr.index(i):
UnboundLocalError: local variable 'i' referenced before assignment

Upvotes: 1

Views: 1617

Answers (1)

cse
cse

Reputation: 4104

You can use recursion method to find the solution.

Following is the solution code. You can see complete code here:

class TreeNode:

    def __init__(self, lValue, lLeft=None, lRight=None):
        self.Value = lValue
        self.Left = lLeft
        self.Right = lRight


def addNode(root, lVal):
    newNode = TreeNode(lVal)
    queue = []
    queue.append(root)
    while(len(queue) > 0):
        node = queue.pop(0)
        if node.Left is None:
            node.Left = newNode
            break

        if node.Right is None:
            node.Right = newNode
            break

        queue.append(node.Left)
        queue.append(node.Right)


def createBinaryTree(lList):
    binaryTree = None
    for i in lList:
        if i is not -1:
            if binaryTree is not None:
                addNode(binaryTree, i)
            else:
                binaryTree = TreeNode(i)

    return binaryTree


def sum(node):
    if node is None:
        return 0
    lLeftVal = sum(node.Left)
    lRightVal = sum(node.Right)

    return (lLeftVal + lRightVal + node.Value)


def solution(binaryTree):
    if binaryTree == None:
        return ""

    if( sum(binaryTree.Left) > sum(binaryTree.Right) ):
        return "Left"
    else:
        return "Right"


def main():
    binaryTree = createBinaryTree([3,6,2,9,-1,10])
    print(solution(binaryTree))


main()

Upvotes: 1

Related Questions