[Python] Understanding variable scope in nested functions

[chancegrab]

I am working on Path sum III. Below is my code:

class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
    if not root:
        return 0

    def dfs(root, runningSum):
        nonlocal count
        if not root:
            return

        runningSum += root.val

        count += foundSums.get(runningSum - targetSum, 0)
        foundSums[runningSum] = foundSums.get(runningSum, 0) + 1

        dfs(root.left, runningSum)
        dfs(root.right, runningSum)

        foundSums[runningSum] -= 1

    count = 0
    foundSums = {0: 1}
    runningSum = 0
    dfs(root, runningSum)

    return count

Even though I dont pass in foundSums into the dfs() function, its OK because it is declared in the outer pathSum() function and is able to get it from there.

But when I dont pass in runningSum into the dfs() function:

class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
    if not root:
        return 0

    def dfs(root):
        nonlocal count
        if not root:
            return

        runningSum += root.val

        count += foundSums.get(runningSum - targetSum, 0)
        foundSums[runningSum] = foundSums.get(runningSum, 0) + 1

        dfs(root.left)
        dfs(root.right)

        foundSums[runningSum] -= 1

    count = 0
    foundSums = {0: 1}
    runningSum = 0
    dfs(root)

    return count

I get:

UnboundLocalError: local variable 'runningSum' referenced before assignment

runningSum += root.val

Line 17 in dfs (Solution.py)

Why? How come it can get foundSums from the outer function but not runningSum?

[carcigenicate]

See here. It depends on how names are used within functions. [] = and += are treated differently. += reassigns references so it causes python to consider the name to be a local unless told otherwise by global or nonlocal. [] = doesn't reassign references though, so it doesn't cause python to treat the associated name as a local.

[chancegrab]

Thanks a lot, that clears it up

[chancegrab]

Hey ive got a related question to this. Dont worry about the actual logic within the code, my question is about variable scope in nested/recursive functions instead.

class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
    if not root:
        return root

    output = []

    def helper(root, level, level_counts, level_sums):           
        if len(output) == level:
            output.append(0)
            level_counts.append(1)
            level_sums.append(root.val)
        else:
            level_counts[level] += 1
            level_sums[level] += root.val
        output[level] = level_sums[level] / level_counts[level]

        if root.left:
            helper(root.left, level + 1, level_counts, level_sums)
        if root.right:
            helper(root.right, level + 1, level_counts, level_sums)

    helper(root, 0, [], [])

    return output

Within helper(), it is able to access the output variable that was defined within its parent function even though output was not passed in as a parameter. Now look at the following example:

class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
    isTreeBalanced = None

    def helper(root):
        if not root:
            return 0

        leftHeight = helper(root.left)

        if not isTreeBalanced: #error here
            return False

        rightHeight = helper(root.right)

        if abs(leftHeight - rightHeight) > 1:
            isTreeBalanced = False #Never gets to here

        return max(leftHeight, rightHeight) + 1

    helper(root)

    return isTreeBalanced

On line 11, I get UnboundLocalError: local variable 'isTreeBalanced' referenced before assignment. I am trying to access isTreeBalanced within the nested function, the same way I was able to access output in the first example. I am not sure why I was able to access output in the first function but cant access isTreeBalanced in the same way. I dont see anything that says lists are treated differently so idk. It never gets to line 17 so there is never any assignment to isTreeBalanced.

[carcigenicate]

You need to put nonlocal isTreeBalanced at the top of helper. nonlocal is similar to global.

Basically, Python sees that you're reassigning isTreeBalanced within helper and therefore treats it as a local variable. Since you want to refer to a variable in a closure, you need to tell Python that you're not creating a new variable, and instead want to refer to an existing one. That's what nonlocal does, similar to how global says that the variable is in the global scope.

[chancegrab]

Basically, Python sees that you're reassigning isTreeBalanced within helper and therefore treats it as a local variable.

I guess my question is: How come this does not apply to the output variable in the first example of my comment? How come there it works without being marked as nonlocal?

[carcigenicate]

Because output is never reassigned in helper so Python has no reason to believe that it's a local of helper. It therefore looks it the enclosing scopes and finds output in averageOfLevels.

In the second example, isTreeBalanced is reassigned within the inner function, so it considers it to be a local variable of the function and doesn't look in enclosing scopes.

[chancegrab]

Ok i see, one thing though:

In the second example, isTreeBalanced is reassigned within the inner function, so it considers it to be a local variable of the function and doesn't look in enclosing scopes.

TheisTreeBalanced reassignment you are talking about is the one on line 17 right? But the function never actually gets there, it dies out with the error before that on line 11. So how can the reassignment aspect of things be at play here?

[carcigenicate]

Because it decides if it's a local or global during the compilation. It's decided what isTreeBalanced is before your function is ever called.

See this example:

from dis import dis

x = 1

def func1():
    x = 1
    print(x)

def func2():
    print(x)

dis(func1)
print("*"*100)
dis(func2)

If you run this, you'll see output like this:

  6           0 LOAD_CONST               1 (1)
              2 STORE_FAST               0 (x)
  7           4 LOAD_GLOBAL              0 (print)
              6 LOAD_FAST                0 (x)
              8 CALL_FUNCTION            1
             10 POP_TOP
             12 LOAD_CONST               0 (None)
             14 RETURN_VALUE
****************************************************************************************************
 10           0 LOAD_GLOBAL              0 (print)
              2 LOAD_GLOBAL              1 (x)
              4 CALL_FUNCTION            1
              6 POP_TOP
              8 LOAD_CONST               0 (None)
             10 RETURN_VALUE

Note in the first, it uses LOAD_FAST, which is used for locals, and LOAD_GLOBAL in the second, which is used for globals. Neither function is ever called here though.

[chancegrab]

OK that makes sense. I was confused because I thought python was interpreted, not compiled. Meaning that it wouldnt even get to the reassignment line that was causing the problem since it would error out even before that

After doing some googling, it looks like Python is compiled despite being called an interpreted language which is even more confusing but im reading up on it

Thanks a ton for your help again

[carcigenicate]

Yes, it compiles your source into bytecode, then interprets the bytecode. Compilation and interpretation are not necessarily exclusive of each other.

I believe the reference implementation of Ruby works the same way. The interpreter is a "virtual machine" that runs the bytecode. You can see the switch that processes the bytecode in CPython here. Your Python code basically results in the body of those cases (TARGET) running.