How to maintain a global variable in recursive function in python?

Question

Unable to keep a track of the variable maxSum, after recursive calls it keeps resetting back to 0, despite passing it as a parameter in calls. The function maxPathSum should return 11 but it's returning 0.

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(node):
    sums = []
    maxPath = []
    maxSum = 0
    recursiveSum(node, 0, maxSum, sums)
    return maxSum


def recursiveSum(node, ssum, maxSum, sums):
    if node == None:
        return
    
    if maxSum < ssum + node.val and node.left == None and node.right == None:
        maxSum = ssum + node.val
            
    sums.append(maxSum)
    
    # traverse left subtree
    recursiveSum(node.left, ssum + node.val, maxSum, sums)
    # traverse right subtree
    recursiveSum(node.right, ssum + node.val, maxSum, sums)


root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(7)
root.right.right = TreeNode(6)
print(maxPathSum(root))

Use (if node is None:) instead of (if node==None:). I don't know if this will solve the problem. But I think this way your code will be better scripted. — Soroosh Noorzad
– Soroosh Noorzad, Commented Apr 24, 2021 at 9:22
@SimranBhake Change return maxSum to return max(sums) in maxPathSum function or try the other solution suggested in the second answer. — quantummind
– quantummind, Commented Apr 24, 2021 at 9:42

quantummind · Accepted Answer · 2021-04-24 09:35:06Z

2

You can achieve your goal by one of the following two modifications.

Since you build a list from the maxSum values, you can simply change the last line of your maxPathSum function so:

def maxPathSum(node):
    sums = []
    maxPath = []
    maxSum = 0
    recursiveSum(node, 0, maxSum, sums)
    return max(sums)

Or you can use the maxSum variable, but for this you must do some small modifications in both functions:

def maxPathSum(node):
    sums = []
    maxPath = []
    maxSum = 0
    maxSum=recursiveSum(node, 0, maxSum, sums)
    return maxSum

def recursiveSum(node, ssum, maxSum, sums):
    if node == None:
        return
    
    if maxSum < ssum + node.val and node.left == None and node.right == None:
        maxSum = ssum + node.val
            
    sums.append(maxSum)
    
    # traverse left subtree
    s=recursiveSum(node.left, ssum + node.val, maxSum, sums)
    if s!=None: maxSum=max(maxSum,s)
    # traverse right subtree
    s=recursiveSum(node.right, ssum + node.val, maxSum, sums)
    if s!=None: maxSum=max(maxSum,s)
    return maxSum

answered Apr 24, 2021 at 9:35

quantummind

2,1461 gold badge15 silver badges20 bronze badges

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

1 Comment

quantummind Over a year ago

@SimranBhake I'm glad to hear that. You can consider to give an upvote to the answer.

Collectives™ on Stack Overflow

How to maintain a global variable in recursive function in python?

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