# Python solution with detailed explanation

• 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
``````

• @gabbu Thank you for sharing this really thoughtful explanation!!
But I'm still confused about the first brute force solution's time complexity, why it is N^2? And if it is a balanced tree, why it is NlgN? Thank you!

• Imagine a balanced tree and think about it this way:

• How many nodes do I need to scan to find all sums which start from the root? Answer: N

• How many nodes do I need to scan to find all sums which start from root.left? Answer: N/2

• How many nodes do I need to scan to find all sums which start from root.right? Answer: N/2

• For the first and second level, we have N + 2(N/2) or 2*N scans. How many total levels do we have in a balanced tree ? Answer lgN. Therefore for a balanced tree it takes N * lg(N)

Imagine a linear list for the worst case

• Using the first node as root, we scan N items

• Using the second node as root, we scan N-1 items

• For all nodes as potential roots or start points, we have: N + (N-1) + (N-2) +... = N^2

• @gabbu Thank you for your really clear explain, so for the brute force part, by saying the time complexity is `N^2` in linear, you mean at the worst case right?
But for balance tree part, did you mean every level needs N scans, so for lgN it needs `N*lg(N)` scans in total? But I think it is not really N scans for each level, for example, at the second level, since the root is exclude, it only scans N-1 times, so I think the total number of scans is `N + (N-1) + (N-2) + (N-4) + ... + N/2` which is `N + (N-2^0) + (N-2^1) + ... + (N-2^(lg(N/2)))`, and that is `(N^2+2N+2)/2`, by thinking this way the time complexity is T(n) = O(N^2).
Do you think the way I think is right? Or where do you think I have made mistake?

• @zzzzzgo Yes for the worst part.

For the balanced part, using what you suggested, we can say the following:
level 1 scans: N
level 2 scans: N-1
level 3 scans: N-1-2 = N-3
level 4 scans: N-1-2-4 = N-7
level h scans : N- N/2

We know h is lg(N). Now we want Big-Oh or upper bound. So we can replace N-1 by N, N-3 by N, ...N-N/2 by N. That means we have N * lg (N). Makes sense?

• This post is deleted!

• 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.

Can anyone help me understand this, please? Thank you

• class Solution(object):
def pathSum(self, root, sum):
if root:
return int(root.val == sum) + self.pathSum(root.left, sum - root.val) + self.pathSum(root.right, sum - root.val)
return 0

why would it not work?

• @hasan-iqbal-anik because the target sum can start from root.left or root right, your recursion excludes that

• @gabbu Don't you need to make a copy of `cache` before passing into `self.helper(root.left, target, so_far+root.val, cache)`? I thought that in python passing a mutable to a function will actually change its value if it gets modified in the function.

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.