CODEWITHSUNDEEP
pythonpython-3.xalgorithmbinary-treedepth-first-search
Michael Torres
Michael Torres

Reputation: 512

Find paths in a binary tree from root to leave what sum, s not working as I expected

I am looking to get

Tree paths with required_sum 23: [[12, 7, 4], [12, 1, 10]]

But instead I am getting

Tree paths with required_sum 23: [[], []]

my code is as follows...

def findPaths(root, val):
  allPaths = []
  findPathsHelper(root, sum, [], allPaths)
  return allPaths

def findPathsHelper(currentNode, sum, currentPath, allPaths):
  if currentNode is None:
    return

  currentPath.append(currentNode.val)
  
  if currentNode.val == sum and currentNode.left is None and currentNode.right is None:
    allPaths.append(currentPath)
  else:
    findPathsHelper(currentNode.left, sum - currentNode.val, currentPath, allPaths)
    findPathsHelper(currentNode.right, sum - currentNode.val, currentPath, allPaths)
 
  del currentPath[-1]

If I change the line where allPaths.append(currentPath) to allPaths.append(list(currentPath)) I get the correct answer but I do not know why.

If I have the following...

l1 = []
l2 = [1, 2, 3]
l1.append(l2)
l1.append(l2)

# then l1 == [[1, 2, 3], [1, 2, 3]]

And if I do this instead...

l1 = []
l2 = [1, 2, 3]
l1.append(list(l2))
l1.append(list(l2))

# then l1 == [[1, 2, 3], [1, 2, 3]]

In which case both are the same, so I do not know why in my code it does not return the correct thing

Upvotes: 0

Views: 53

Answers (1)

Gonzales Gokhan
Gonzales Gokhan

Reputation: 492

I think your problem is you are deleting current path item before copying it. Python lists are “pass-by-object-reference”

del currentPath[-1]

also findPathsHelper(root, val, []) should be used instead of findPathsHelper(root, sum, [], allPaths) you are not passing the value .

to test things , i created a demo project and used a global variable and seems like it is working then.

class Node(object):
    def __init__(self, value,left=None, right=None):
        self.val = value
        self.left = left
        self.right = right

    def __str__(self):
        return '{:d} {:d}'.format(self.value)
allPaths=[]
def findPaths(root, val):
    global allPaths
    allPaths=[]
    findPathsHelper(root, val, [])
    return allPaths

def findPathsHelper(currentNode, sum, currentPath):
    if currentNode is None:
        return

    currentPath.append(currentNode.val)
    
    if currentNode.val == sum and currentNode.left is None and currentNode.right is None:
        global allPaths
        allPaths.append(currentPath.copy())
    else:
        findPathsHelper(currentNode.left, sum - currentNode.val, currentPath)
        findPathsHelper(currentNode.right, sum - currentNode.val, currentPath)
    
    del currentPath[-1]

if __name__ == "__main__":
    root=Node(12,Node(7,Node(4),Node(10)),Node(1,Node(9),Node(10)))
    result=findPaths(root,23)
    print(allPaths)

Upvotes: 1

Related Questions