CODEWITHSUNDEEP
pythonalgorithmrecursiondata-structures
Simran Bhake
Simran Bhake

Reputation: 117

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

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))

Upvotes: 1

Views: 506

Answers (1)

quantummind
quantummind

Reputation: 2136

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

Upvotes: 2

Related Questions