Paths with Sum
problem
You are given a binary tree in which each node contains an integer value(which might be positive or negative). Design an algorithm to count the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
how to use
If I can check the all path I can find the solution in O(n2). So I suggest the optimized one. In the optimized code, I use hash-table like two sum problem. This hash-table maps from a runningSum to the number of times we’ve seen that sum. In each node, I can find the count of root path to satisfy the condition in O(1) . So time complexity is O(n) and space complexity is O(n) to have a hash table.
