[FIXED] Change in a list in Python when it is called recursively

Issue

I was solving some problems on a binary tree and I got stuck in the question Lowest Common Ancestor in a Binary Tree | Set 1.

I am using Python to solve the question.

My question is like in the case where we want to find the common ancestor between 4 and 5, how when the function is called first time [1,2,4] is returned...

How.... shouldn't 3, 6, 7 be also be appended in the list along with 1,2,4 when (root.right!= None and findPath(root.right, path, k) is called recursively.

PS: Please refer to the Python code given in the link

Solution

The code you're asking about appears to be the findPath function, copied here:

# Finds the path from root node to given root of the tree.
# Stores the path in a list path[], returns true if path
# exists otherwise false
def findPath( root, path, k):
 
    # Baes Case
    if root is None:
        return False
 
    # Store this node is path vector. The node will be
    # removed if not in path from root to k
    path.append(root.key)
 
    # See if the k is same as root's key
    if root.key == k :
        return True
 
    # Check if k is found in left or right sub-tree
    if ((root.left != None and findPath(root.left, path, k)) or
            (root.right!= None and findPath(root.right, path, k))):
        return True
 
    # If not present in subtree rooted with root, remove
    # root from path and return False
      
    path.pop()
    return False

(Source: https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/)

And you're confused about how the path output argument works. That's a fair question, as the algorithm is a little indirect about how it builds that list.

Let's look at all of the return codepaths, and specifically focus on what's happening to path when this happens. I've copied the above code without the comments, focusing just on the main logic of the function. The comments are mine. I've also renamed "root" to "current" as this makes the method more clear.

def findPath(current, path, k):
 
    # Put the current node's key at the end of the path list.
    path.append(current.key)
 
    # Return immediately if the current node is the target.
    if current.key == k:
        return True
 
    # Return immediately if one of the current node's children contains the target.
    if ((current.left != None and findPath(current.left, path, k)) or
            (current.right!= None and findPath(current.right, path, k))):
        return True
 
    # Remove the current node's key from the path list.
    path.pop()
    return False

So, we can think of this function as essentially doing the following (in pseudocode):

def findPath(current, path, target):
  path += current.key
  if (current or its children contain target):
    return True
  else 
    path -= current.key
    return False

Note that only in the "happy" case, where current or its children contain target, do we leave current.key in path. In all other code paths, we remove current.key from path. So, in the end, path will contain exactly the keys between root and target.

Answered By - Welbog