CODEWITHSUNDEEP
pythonalgorithmbinary-tree
Ragesh Kr
Ragesh Kr

Reputation: 1733

Sum of paths III - Leetcode

Given a target sum , we need to find the path count i.e total no of paths. Also it is given that , it is not necessary the path needs to start from the root node.

I came across a solution , for this question. I am also able to understand 85% of the solution.

Solution :

def pathCounter(node,currPath,_sum):
    if node is None:
        return 0
    path = []
    currPath.append(node.data)
    
    pathSum , pathCount = 0, 0
      
    #Unable to understand below for loop
    for i in range(len(currPath)-1,-1,-1):
        
        pathSum +=currPath[i]
        path.append(currPath[i])
        
        
        if pathSum==_sum:
            pathCount+=1
            #print(path)
            
    pathCount+= pathCounter(node.left,currPath,_sum)
    pathCount+= pathCounter(node.right,currPath,_sum)
    
    del currPath[-1]
    
    
    return pathCount

The issue I have is, I am unable to understand , why the for loop is set to iterate in reverse order and not in normal order ?

How does this affect the problem ?

Upvotes: 0

Views: 237

Answers (1)

trincot
trincot

Reputation: 351298

The reason is that when you perform the loop in the forward direction, the if condition is going to check the sums that represent a prefix of currPath, instead of a postfix.

As the recursion appends node values at the end of currPath it does not make sense to repeat the check of prefix sums (as that would already have been checked earlier on). The prefix sums would always include (the value of) the root node, while we cannot assume the root node must be included in a solution.

The purpose of the recursion is to include the newly visited node in all sum-checks, and since that new node is sitting at the end of currPath, the sum should accumulate from the end in a backwards direction.

For example:

Let's say there is a downward path in the tree with these values: 10 - 5 - 3 - 1, and that we need to find a sum of 8. Then in the first level of recursion, we visit 10, and in the next we visit 5. At this point we verify these sums:

* 5
* 5 + 10

Neither gives a match, so we recur deeper and visit 3. Now we check these sums:

* 3
* 3 + 5 => It's a match!
* 3 + 5 + 10

If at this stage we would have done a forward loop, we would have checked these sums:

* 10
* 10 + 5
* 10 + 5 + 3

None would match, and we would never have checked any sum that does not include the root.

Upvotes: 1

Related Questions