CODEWITHSUNDEEP
pythonrecursiontreebinary-search-treebreadth-first-search
able-leopard
able-leopard

Reputation: 115

Updating variables in recursion

This is referring to this leetcode question here: https://leetcode.com/problems/path-sum-iii/

Basically I am given a binary tree in which each node contains an integer value. I have to find the number of paths that sum to a given value.

Building up a sample tree here

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

root = TreeNode(12)
root.left = TreeNode(7)
root.right = TreeNode(1)
root.left.left = TreeNode(4)

root.right.left = TreeNode(10)
root.right.right = TreeNode(5)

This is my solution using recursion

def count_paths(root, S):

    cache = {0:1}

    def helper(node, S:int, curr_path:int, cache:dict, result:int):

        if not node:
            return result

        curr_path += node.val
        prev_path = curr_path - S

        result += cache.get(prev_path, 0)
        cache[curr_path] = cache.get(curr_path, 0) + 1

        my_node = None
        if node != None:
            my_node = node.val 

        print("node: {}, curr: {}, prev: {}".format(my_node, curr_path, prev_path))                
        print(cache)
        print(result)

        helper(node.left, S, curr_path, cache, result)
        helper(node.right, S, curr_path, cache, result)

        return result

    return helper(root, S, 0, cache, 0)

Basically I don't understand why the recursive function is not updating my result variable but its updating my cache variable.

Is there a correct way to update the result variable?

This is the test case

count_paths(root, 11)

I printed each line of the results

node: 12, curr: 12, prev: 1
{0: 1, 12: 1}
0
node: 7, curr: 19, prev: 8
{0: 1, 12: 1, 19: 1}
0
node: 4, curr: 23, prev: 12
{0: 1, 12: 1, 19: 1, 23: 1}
1
node: 1, curr: 13, prev: 2
{0: 1, 12: 1, 19: 1, 23: 1, 13: 1}
0
node: 10, curr: 23, prev: 12
{0: 1, 12: 1, 19: 1, 23: 2, 13: 1}
1
node: 5, curr: 18, prev: 7
{0: 1, 12: 1, 19: 1, 23: 2, 13: 1, 18: 1}
0
Tree has paths: 0

Can someone please explain what I am missing here? I have a feeling I am making a fundamental recursion mistake here. I know I make a class and just store the variable there but I am really find to understand how to do recursion properly. Thanks so much!

Upvotes: 0

Views: 3961

Answers (1)

Matvei
Matvei

Reputation: 323

tldr:

Python defaults to pass by reference, but since integers are immutable, it's like those are passed by copy. The easiest workaround here would be something like result += helper(...), or result = helper(...).

Long answer:

In many languages (like C++ and Java), passing arguments defaults to passing copies of those objects. If you want to pass an object into a function and have it updated for use outside that function's context, you have to pass a pointer (or something similar).

Python, on the other hand, defaults to pass by reference. This would make you think your result variable would be updated in place, right?

The problem is that result, being an integer, is immutable. So, when you change its value within one of the recursive calls, it doesn't change the result variable for the other calls. It just reassigns the label result to a new integer value, but only in that function call's scope. The new value is lost once the function returns.

If you want to update an integer variable's value with a function call, you have to either set the variable to the return value of the function (see tldr above), or wrap the integer in a mutable object (see Passing an integer by reference in Python).

Upvotes: 3

Related Questions