Path Sum iii | LeetCode 437 | C++, Java, Python

**** CORRECTION: TC is O(n^2), since from every node we are triggering a new pathSum_a(), which traverses tree rooted at that node.

**** Best Books For Data Structures & Algorithms for Interviews:**********
*****************************************************************************

August LeetCoding Challenge | Problem 8 | Path Sum iii | 8 August,
Facebook Coding Interview question,
google coding interview question,
leetcode,
Path Sum iii,
Path Sum iii c++,
Path Sum iii Java,
Path Sum iii python,
Path Sum iii solution,
437. Path Sum iii,

#CodingInterview #LeetCode #AugustCodingChallenge #Google #Amazon #binaryTree #pathsum

[koteshmeesala]

I saw other solutions. They used memoization or caching..I think this can be further optimized

[andriesrunkat]

Is it the complexity supposed to be O(2^n) ?

[mohitbambani]

For a full binary tree complexity will be O(nlogn) and for a skew one O(n^2)??? If wrong please elaborate...

[masoomyf]

it is failing for new test case added where target sum is zero and tree has only left child with number greater than zero.
tree:

[rajeshg]

Tried avoiding multiple traversals - Extension of "How many subset of array for given sum?"
class Solution:
def __init__(self):
self.freq = dict()
self.counter = 0

def search_sum(self, node, k, current_sum, parent_node_val):
if not node:
return
# print(node.val, current_sum, self.freq)
if node.val == k or (current_sum + node.val) == k: self.counter += 1
if (current_sum + node.val) - k in self.freq:
if (current_sum + node.val) - k == 0 or (current_sum + node.val) - k != current_sum:
self.counter += self.freq[(current_sum + node.val) - k]
else:
self.counter += self.freq[(current_sum + node.val) - k] - 1

self.freq[current_sum + node.val] = self.freq.get(current_sum + node.val, 0) + 1

if node.left: self.search_sum(node.left, k, current_sum+node.val, node.val)
if node.right: self.search_sum(node.right, k, current_sum+node.val, node.val)

self.freq[current_sum + node.val] -= 1
if self.freq[current_sum + node.val] == 0:
del self.freq[current_sum + node.val]

return


def pathSum(self, root: TreeNode, sum: int) -> int:
self.search_sum(root, sum, 0, None)
return self.counter

[abhineykumar]

how is this o(n)??? can anyone explain?

[anoushehshahmirza]

The exact same code for C#, does not pass all testcases. I was wondering if you have any idea about that :(

[shabarinathpabba]

around approximately 2:15, you say, "there are two things" how did you come up with that thought, there are two cases?

[SaiPavanPothuri]

The above code fails if we have negative nos in the tree.
Failing for the below test case.
testcase:
[1, -2, -3, 1, 3, -2, null, -1]
-1

[vijayakumareyunni]

Good attempt to explain. But, I do have some comments. Cases - 1&2 are written on board in one order, but, explained in opposite order leading to confusion. Very slow explanation from the beginning and I had to fast-forward to save time. Last, python code is written poorly - Indentation is the key in python, but, copy & paste made it worse.

[pranaynagpure]

quick update take long sum in pathSum_a function due to overflow condition

[namankeshari]

its time complexity is O(n logn) and not O(n).

[muraliKrishnaanimi]

Can you share the gear you use for teaching on board?

[davidlee]

There is code duplication in the python solution

[akshaykumarmalathkar]

The logic is correct but the test cases have been updated in leetcode and this code fails for the below test case:

0
This is because there is integer overflow and hence need to use long. Python coders need not worry about this though.

[rishisharma]

My Solution(96% faster)

class Solution {
int cnt = 0;
vector<int> v;
public:
void traverse(TreeNode* root, int sum, int currSum){
if(root == NULL)
return;
v.push_back(root->val);
currSum += root->val;
int s=0;
for(int i=0; i<v.size(); i++){
if(currSum-s == sum)
cnt++;
s += v[i];
}
traverse(root->left, sum, currSum);
traverse(root->right, sum, currSum);
currSum -= root->val;
v.pop_back();
}
int pathSum(TreeNode* root, int sum) {

traverse(root, sum, 0);
return cnt;
}

[muskanrai]

Java Solution failed for the following Testcase


Input
root =

targetSum =0

Output
2
Expected
0

[vaibhavmalik]

O(n) soln and easy to understand


Void pathSumUtil(TreeNode* root, int sum, vector<int>& path, int& count) {
if (root==NULL)
return;
path.push_back(root->val);
pathSumUtil(root->left, sum, path, count);
pathSumUtil(root->right, sum, path, count);
int curr_sum = 0;
for (int i=path.size()-1; i>=0; i--) {
curr_sum += path[i];
if (curr_sum == sum) count++;
}
path.pop_back();
}

int pathSum(TreeNode* root, int sum) {
vector<int> path;
int count=0;
pathSumUtil(root, sum, path, count);
return count;
}