Python: reference variable in nested function's outer scope (not global)

Question

I'm trying to recurse a tree and track the path of the traversal up to the point where I find an element that I'm looking for. However, I encounter two issues:

1. While my current code returns the correct solution, it's a bit hacky. I have to push the current path that's being traversed to final_path, then return final_path[0]. If I just try to set final_path = path, where final_path is defined in the outer scope, it doesn't work. How can I reference the outer scope of the nested function?

2. In the event the value is not in the tree, I end up with the entire tree traversed in pre-order fashion. Is there any way to structure the code so that I could say "If, at the end of the traversal, we haven't found the target element, then just return [] instead of the full path". I realize that I can just loop through and check each element, but this seems very redundant.

Code:

lftlft = {'val': 3, 'left': None, 'right': {'val': 100, 'left': None, 'right': None}}
rtrt = {'val': 5, 'left': None, 'right': None}
lft = {'val': 2, 'left': lftlft, 'right': {'val': 99, 'left': None, 'right': None}}
rt = {'val': 4, 'left': None, 'right': rtrt}
T = {'val': 1,'left': lft, 'right': rt}

def get_path(root, data, path):
    final_path = []

    def pre_order(tree, path):
        if tree is None:
            return

        path.append(tree['val'])

        if tree['val'] == data:
            final_path.append(path)
            return True

        return pre_order(tree['left'], path[:]) or pre_order(tree['right'], path[:])

    pre_order(root, [])
    print('finalpath', final_path)
    return final_path[0]

get_path(T, 99, [])

Answer 1

In Python 3.x, you just have to use the keyword nonlocal.

You use it where you'd use global: at the start of your inner function:

def get_path(root, data, path):
    final_path = ...

    def pre_order(tree, path):
        nonlocal final_path
        ...
    ...

    return final_path

Even in Python 2.x, just referencing a variable would automatically grant you read access to the variable - but never write access. Note that if the object referenced is a mutable object, like a list or a dictionary, you can further modify it inside the inner function.

With the introduction of the nonlocal keyword in Python 3.0, you can have full write access to a variable defined in an outer function scope. ]

Your hack of having the inner function writting to a fixed element in an outer-scope list is perhaps the best way to work around it in Python 2.x.

Answer 2

I realized I don't have to iterate to check if it's found. Don't know why I didn't think of adding a flag earlier.

rtrt = {'val': 5, 'left': None, 'right': None}
lft = {'val': 2, 'left': lftlft, 'right': {'val': 99, 'left': None, 'right': None}}
rt = {'val': 4, 'left': None, 'right': rtrt}
T = {'val': 1,'left': lft, 'right': rt}


def get_path(root, data, path):
    final_path = []
    found = False

    def pre_order(tree, path):
        if tree is None:
            return

        path.append(tree['val'])

        if tree['val'] == data:
            nonlocal final_path, found
            final_path = path
            found = True
            return found

        return pre_order(tree['left'], path[:]) or pre_order(tree['right'], path[:])

    pre_order(root, [])
    if not found:
        return []

    return final_path

get_path(T, 999, [])

Answer 3

I think it's because when you call pre-order from get_path you don't capture the return value.

The following appears to get the same result as your code example for me, and if I change the value 99 to some other number, I get a return value of None

lftlft = {'val': 3, 'left': None, 'right': {'val': 100, 'left': None, 'right': None}}
rtrt = {'val': 5, 'left': None, 'right': None}
lft = {'val': 2, 'left': lftlft, 'right': {'val': 99, 'left': None, 'right': None}}
rt = {'val': 4, 'left': None, 'right': rtrt}
T = {'val': 1,'left': lft, 'right': rt}

def get_path(root, data, path):

    def pre_order(tree, path):
        if tree is None:
            return

        path.append(tree['val'])

        if tree['val'] == data:
            return path
        return pre_order(tree['left'], path[:]) or pre_order(tree['right'], path[:])

    desired_result = pre_order(root, [])
    return desired_result

print (get_path(T, 99, []))

Answer 4

This is an XY problem. You can do what you're asking, but it's essentially adding global state to your function. Well, the use of final_path already means you are using global state, which you should avoid where possible (and it is possible in this case).

There are a couple of ways you can get around your problem. First, rather than appending, you can extend final_path. That is, replace final_path.append(path), with final_path.extend(path). Rather than adding path as an element to final_path, this adds all the elements of path as elements of final_path. But you're still using global state, which isn't great.

Instead You can use the "truthful-ness" of Python objects so that you can return different types. That is, rather than returning True, you can return the path itself, and only append the current val if a path is returned. And if you didn't find a path, then return a false-like value such as []. This will create a reversed path, but you can just reverse the path at the end. eg.

def get_path(root, data, path):

    def pre_order(tree):
        if not tree:
            # base case, data not found
            return [] # counts as false
        elif tree['val'] == data:
            # base case, found data
            return [data] # counts as true
        else:
            # recursive case
            path = pre_order(tree['left']) or pre_order(tree['right'])
            if path:
                # data was found, add the current val to the path
                path.append(tree['val'])
            return path

    final_path = pre_order(root)
    final_path.reverse()
    print('finalpath', final_path)
    return final_path

Finally, the answer to how you want to write your solution is to use the keyword nonlocal. This allows you to changed the object that final_path points to, not just mutate the object. eg.

def f():
    x = 1
    def g():
        nonlocal x
        x = 2
    g()
    print("x =", x) # prints x = 2