**Path Sum III** https://leetcode.com/problems/path-sum-iii/

**Brute Force Solution**

- The simplest solution is to traverse each node (preorder traversal) and then find all paths which sum to the target using this node as root.
- The worst case complexity for this method is N^2.
- If we have a balanced tree, we have the recurrence: T(N) = N + 2T(N/2). This is the merge sort recurrence and suggests NlgN.

```
class SolutionBruteForce(object):
def find_paths(self, root, target):
if root:
return int(root.val == target) + self.find_paths(root.left, target-root.val) + self.find_paths(root.right, target-root.val)
return 0
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
if root:
return self.find_paths(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
return 0
```

**Two Sum Method: Optimized Solution**

- A more efficient implementation uses the Two Sum idea. It uses a hash table (extra memory of order N). With more space, it gives us an O(N) complexity.
- As we traverse down the tree, at an arbitrary node N, we store the sum until this node N (sum_so_far (prefix) + N.val). in hash-table. Note this sum is the sum from root to N.
- Now at a grand-child of N, say G, we can compute the sum from the root until G since we have the prefix_sum until this grandchild available.We pass in our recursive routine.
- How do we know if we have a path of target sum which ends at this grand-child G? Say there are multiple such paths that end at G and say they start at A, B, C where A,B,C are predecessors of G. Then sum(root->G) - sum(root->A) = target. Similarly sum(root->G)-sum(root>B) = target. Therefore we can compute the complement at G as sum_so_far+G.val-target and look up the hash-table for the number of paths which had this sum
- Now after we are done with a node and all its grandchildren, we remove it from the hash-table. This makes sure that the number of complement paths returned always correspond to paths that ended at a predecessor node.

```
class Solution(object):
def helper(self, root, target, so_far, cache):
if root:
complement = so_far + root.val - target
if complement in cache:
self.result += cache[complement]
cache.setdefault(so_far+root.val, 0)
cache[so_far+root.val] += 1
self.helper(root.left, target, so_far+root.val, cache)
self.helper(root.right, target, so_far+root.val, cache)
cache[so_far+root.val] -= 1
return
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
self.result = 0
self.helper(root, sum, 0, {0:1})
return self.result
```