CODEWITHSUNDEEP
pythonrecursiontree
Jess
Jess

Reputation: 73

Tracking and updating value in a recursive function

Found this code online which can be used to find the maximum value in a tree between two leaf nodes:

INT_MIN = -2**32

class Node: 
    def __init__(self, data): 
        self.data = data 
        self.left = None
        self.right = None

def maxPathSumUtil(root, res): 
    if root is None: 
        return 0

    if root.left is None and root.right is None: 
        return root.data 

    ls = maxPathSumUtil(root.left, res) 
    rs = maxPathSumUtil(root.right, res) 

    # If both left and right children exist 
    if root.left is not None and root.right is not None:      
        res[0] = max(res[0], ls + rs + root.data) 
        return max(ls, rs) + root.data 

    # If any of the two children is empty, return 
    # root sum for root being on one side 
    if root.left is None: 
        return rs + root.data 
    else: 
        return ls + root.data 

def maxPathSum(root): 
        res = [INT_MIN] 
        maxPathSumUtil(root, res) 
        return res[0]

My question is in regards to res[0]. Why use a list with only one value to keep track of the maximum value at that node? I tried changing it to a regular integer and it does not get updated properly. It returns the wrong value. So why does using a list with a single value works versus using a regular integer to keep track of the maximum value during a recursive function?

Upvotes: 1

Views: 1210

Answers (1)

TrebledJ
TrebledJ

Reputation: 8997

The res list acts as reference to the original object, so that even without returning the object, the function can mutate it.

Note: If you're familiar with C/C++, this is like passing a reference using <type> &<var_name> into the function.

The following example illustrates this:

>>> def func(ref):
...  ref.append(1)
... 
>>> list_ = [1, 2, 3]
>>> func(list_)
>>> list_
[1, 2, 3, 1]

As seen, the function changes the object in-place.

This is primarily due to list_ and ref referring to the same id.

>>> def func(ref):
...  ref.append(1)
...  print('Ref:', id(ref))
... 
>>> list_ = [1, 2, 3]
>>> id(list_)
4421621704
>>> func(list_)
Ref: 4421621704

Since both list_ and ref refer to the same id, any changes to the list will propagate throughout other lists with the same id's.

>>> a = [1, 2, 3]
>>> b = a
>>> b.append(10)
>>> id(a), id(b)
(4421619848, 4421619848)
>>> a, b
([1, 2, 3, 10], [1, 2, 3, 10])

Note that a and b have the same id, they thus refer to the same list object. This justifies why a 10 was appended to a.

Upvotes: 1

Related Questions