Python: how does list work within recursion

Question

I'm trying to print the path(from root to leaf node) for a binary tree. I was trying to use a list as input to record the path and return it.

However, the return value is empty, I can see the path is being generated correctly, by printing the path at the recursion function.

Case 1:

Input:
res = printPath(root, node,[]) 

Output:
res = []

My question is, how does list work with recursion, how does python handle the scope of it?

Case 2:

Input:
p_ = []

res = printPath(root, node, p_)

Output:
res != []

also res is not equal to the final path, which inside the recursion, can you please let me know why is that. Eg, path = [3, 5], res = []

res is not empty but it will have some middle value of the recursion. I guess, in this case, the list is treated as a pointer.

If you can let me know the difference between these 2 cases, it would be great.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def printPath(self, root, node, path):
        if root:
            # print root.val, node
            if root.val == node:
                path.append(node)
                print path
                return path
            if root.left:
                path.append(root.val)
                self.printPath(root.left, node, path)
            if root.right:
                path.append(root.val)
                self.printPath(root.right, node, path)

    def lowest_main(self, root, p):
        # print root.val, p
        p_ = []
        print self.printPath(root, 5, p_)
        # print p_

There are a few issues with the printPath function you have included: self is not the leading argument, so you should use printPath instead of self.printPath. Second is that if you are trying to assign res with results of printPath, as implemented, printPath does not return a list or any value thus res will always equal to None. Yes you can append nodes (or whatever) to path that is provided, and yes the same assignment will get passed as you have specified in the code you have included. — metatoaster
– metatoaster, Commented Mar 1, 2019 at 4:47
Hi @metatoaster, I tried to do the following, however the print is NONE p_ = []; print self.printPath(root, 5, p_) if I print the path within the return block if root.val == node: path.append(node);print path;return path, I can see the correct path. do you have any idea why this is happening? — Ian Zhang
– Ian Zhang, Commented Mar 1, 2019 at 5:20
My apologies. I missed your return path statement. However, the results of the recursive printPath isn't being returned which means that invocations using a root and node that are not equal will not have a return value. This is where I was confused about when I thought your code did not have a return statement. — metatoaster
– metatoaster, Commented Mar 1, 2019 at 5:30

fountainhead · Accepted Answer · 2019-03-01 16:15:05Z

1

Case 1:

Here, you are passing a list object having zero elements, as argument to the "root invocation" of printPath().

Inside this invocation, that empty list can be accessed with the parameter called path.

During the execution of the function, that empty list would become non-empty.

But once you've exited this "root invocation" of the function, that parameter called path, which is referring to the (now non-empty) list, goes out of scope.

Now, you are left with no other variable (or name) referring to that non-empty list, so there is no way for you to actually look at the non-empty path and celebrate.

Case 2:

Here also, you are passing an empty list object to your "root invocation" of printPath(). But the difference is that even before you invoke printPath(), you have ensured that there is one more variable (or name) called p_, which is pointing to the same empty list object that you are passing to the "root invocation". As with Case 1, inside the invocation, the empty list object is accessed with the parameter name path. As with Case 1, this empty list will become non-empty during the execution. As with Case 1, when the root invocation eventually completes execution and returns control, the parameter named path which was pointing to the (now non-empty) list object, will go out of scope, but you are still left with one more variable called p_, pointing to the same (now non-empty) list object.

Reason why print self.printPath(root, 5, p_) prints None:

Let's take a simple tree, in which the root node has a value of 0, and the left child has a value of 5. Assume that there are no other nodes in the tree.

What happens in your root invocation of printPath():

You will first check if root.val == node. The test will fail.

You will next check if root.left. The test will pass. You will enter that if block, append 0 to path, and make your second invocation of printPath(). Now, carefully note the fact that the second invocation is made from within the first invocation. The first invocation has not yet completed. In fact, at that instant, the first invocation as well as the second invocation are both in a state of having partially executed. Correct? And the first invocation and second invocation at two different line numbers. The first invocation is at the line where printPath() is invoked for the left child, and the first invocation is just about to start executing at the first line of printPath(). Correct?

What happens next?

The second invocation also checks if root.val == node. This time, the test succeeds, and it enters the if block, appends 5 to path, and returns path.

But where does this returned value go? To the place where this second invocation happened ! Which, if you remember, is another line in printPath(). At that line, you are invoking printPath(), but not capturing its return value in any variable -- you are just ignoring its return value. So, the 0 5 string returned by the second invocation is being ignored. The execution of the first invocation continues until it reaches the last line of printPath(). At the last line, there is no other return statement. So, in the absence of an explicit return statement, any Python function will return None. So, this first invocation will return None, to the place where your first invocation happened (I think that is in lowest_main()).

The first invocation is printing this None value.

How to correct:

To correct this, please change the following line:

self.printPath(root.left, node, path)

to this:

return self.printPath(root.left, node, path)

Similarly, please change the following line:

self.printPath(root.right, node, path)

to this:

return self.printPath(root.right, node, path)

edited Mar 1, 2019 at 16:15

answered Mar 1, 2019 at 6:06

fountainhead

3,7421 gold badge11 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Ian Zhang Over a year ago

Hi @fountainhead, I tried to do the following, however, the print is NONE p_ = []; print self.printPath(root, 5, p_) if I print the path within the return block if root.val == node: path.append(node);print path;return path, I can see the correct path. do you have any idea why this is happening? Reading your post, I understand the first case, but for the second case, I'm still confused by the test case over here.

fountainhead Over a year ago

@IanZhang: From your comments, it looks like you have printPath as a method of some class, but looking at your post, that was not at all evident. It would be better if you could check again whether you've posted all relevant parts of the code, including the place where you actually invoke functions, your initialization of the root node, etc.

Ian Zhang Over a year ago

I posted the class, can you please help me check it out. Thanks

fountainhead Over a year ago

@IanZhang: Please see my answer edited with complete explanation.

U13-Forward · Accepted Answer · 2019-03-01 04:53:11Z

1

Because:

>>> [].append(2)
>>> []
[]
>>> l=[]
>>> l.append(2)
>>> l
[2]
>>>

Because [] isn't stored anywhere, so won't update any variable, that's why.

[] would be kept in memory after append, but no way to access it.

answered Mar 1, 2019 at 4:53

U13-Forward

71.8k15 gold badges100 silver badges125 bronze badges

1 Comment

Ian Zhang Over a year ago

Hi @U9-Forward, thanks for your answer, however, when I do the second test, I'm still getting res=[], path !=[], can you please help me out on it?

Collectives™ on Stack Overflow

Python: how does list work within recursion

2 Answers 2

4 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related