CODEWITHSUNDEEP
pythonbinary-tree
Ragesh Kr
Ragesh Kr

Reputation: 1713

Binary Tree Path Sum in Python

The question is in a binary tree, I need to print the paths that sum up to the target number. I got the logic right , with the help of google. But I have trouble in understanding one line of the code.

Code :

class Node:
    
    def __init__(self,data):
        
        self.data = data
        self.left = None
        self.right = None
        
class Tree:
    
    def __init__(self,root):
        self.root = Node(root)


def findPaths(root,tot):
    
    if root is None:
        return None
    
    all_paths = []
    
    findPathsRecur(root,tot,[],all_paths)
    
    return all_paths


def findPathsRecur(node,tot,currPath,all_paths):
    
    #global all_paths
    
    if node is None:
        return None
    
    #Append node to current path
    
    currPath.append(node.data)
    
    
    if node.data == tot and (node.left is None and node.right is None):
       
        all_paths.append(list(currPath)) #=> This is where I have trouble
        
        
    else:
        
        findPathsRecur(node.left,tot-node.data,currPath,all_paths)
        findPathsRecur(node.right, tot-node.data,currPath,all_paths)
        
    del currPath[-1]
    
    return all_paths

In the above code only if I cast currPath inside a list I am getting the correct output, else all I get is an empty list. I tried debugging using type() function even that returns the type of currPath as list only. What is the necessity or why should I use list(currPath). Please find the output below.

Output while using `all_paths.append(list(currPath))`:

[[1, 7, 4], [1, 9, 2]]

Output while using `all_paths.append(currPath)`:

[[], []]

Upvotes: 0

Views: 205

Answers (1)

Arsal
Arsal

Reputation: 447

It's happening because with all_paths.append(currPath), currPath is being passed as a pointer but when you use list(currPath) you're basically adding its copy to all_paths. To confirm this, you can try: all_paths.append(currPath.copy()), it'll give you correct output.

When you append a list1 to another list2, you're basically appending a reference of list1 to list2. If list1 is modified anywhere else, it'll reflect on list2 too. To confirm this:

a = []
a.append(1)
a.append(2)
b = []
b.append(a)
print (b)  #   OUTPUT: [[1, 2]]
del a[0]
print (b)  #   OUTPUT: [[2]]

Upvotes: 1

Related Questions