Python solution with detailed explanation


  • 20
    G

    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
    

  • 2
    Z

    @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!


  • 6
    G

    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


  • 0
    Z

    @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?


  • 0
    G

    @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?


  • 0
    I
    This post is deleted!

  • 0
    I

    @gabbu said in Python solution with detailed explanation:

    • 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


  • 0
    H

    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?


  • 0
    A

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


  • 0
    N

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


  • 0
    K
    This post is deleted!

Log in to reply
 

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