Trees & Hashmap— Path Sum III

Medium : https://leetcode.com/problems/path-sum-iii/

Problem Statement:

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

Questions to ask to interviewer: does the path need to start at root? Does the path need to end at leaf? If not, then we have two problems in this question.

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

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
Return 3. The paths that sum to 8 are:
1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

My Inception

I feel it was a bit difficult. It requires knowledge of two kinds of solutions

1. Preorder traversal of Binary Tree using stack. Here, we use the stack to pass information from root to the children nodes of the tree, using a depth first approach. We will be using the recursive implementation of the algorithm.(https://takeitoutamber.medium.com/bst-sum-root-to-leaf-numbers-a8f64e3d9ba1)
2. Prefix Sum : Uses a Hashmap to keep track of a cumulative number along an array. (https://takeitoutamber.medium.com/array-subarray-sum-equals-k-32e92181ecd3)

Please read both the solutions first before trying this out.

Solution :

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        count = 0
        hmap = defaultdict(int)
        def preorder(node, rtohere_cum_sum):
            nonlocal count
            if node:
                # current prefix sum
                rtohere_cum_sum += node.val
                
                # Situation 1, k which is path from root to node
                if  rtohere_cum_sum == sum:
                    count += 1
                # Situation 2, # number of times the curr_sum − k has occurred already, 
                # determines the number of times a path with sum k 
                # has occurred up to the current node
                if rtohere_cum_sum - sum in hmap:
                    count += hmap[rtohere_cum_sum - sum]
                
                # add the current sum into hashmap
                # to use it during the child nodes processing
                hmap[rtohere_cum_sum] += 1    
                
                # process left subtree
                preorder(node.left, rtohere_cum_sum)
                 # process right subtree
                preorder(node.right, rtohere_cum_sum)
            
                # remove the current sum from the hashmap
                # in order not to use it during 
                # the parallel subtree processing
                hmap[rtohere_cum_sum] -= 1
                
        preorder(root, 0)
        return count

Success

def pathSum(self, root: TreeNode, sum: int) -> int:
        stack = [(root, 0)]
        count = 0
        hmap = {}
        
        while stack:
            node, curr_cum_sum = stack.pop()
            
            # remove the current sum from the hashmap
            # in order not to use it during 
            # the parallel subtree processing 
            if node and node.val == "curr_cum_sum":
                if curr_cum_sum in hmap:
                    hmap[curr_cum_sum] -= 1
                continue
            
            if node:
                # if node.val == sum:
                #     count += 1   
                    
                # current prefix sum
                curr_cum_sum += node.val
                
                # Situation 1 :here is the sum we're looking for
                if curr_cum_sum == sum:
                    count += 1
                
                # Situation 2: number of times the curr_sum − k has occurred already, 
                # determines the number of times a path with sum k 
                # has occurred up to the current node
                if curr_cum_sum - sum in hmap:
                    count += hmap[curr_cum_sum - sum]
                
                # add the current sum into hashmap
                # to use it during the child nodes processing
                if curr_cum_sum not in hmap:
                    hmap[curr_cum_sum] = 1
                else:
                    hmap[curr_cum_sum] += 1
                
                
                if node.right or node.left:
                    # insert a fake node to mark "complete" the LR traversal of a node 
                    # we will use this to pop the cumsum from the hmap of this node.
                    stack.append((TreeNode("curr_cum_sum"), curr_cum_sum))
                    # push right subtree
                    stack.append((node.right, curr_cum_sum))
                    # push left subtree, so that it gets popped before the right subtree
                    stack.append((node.left, curr_cum_sum))
                
                # remove the current sum from the hashmap
                # in order not to use it during 
                # the parallel subtree processing 
                if not node.right and not node.left :
                    hmap[curr_cum_sum] -= 1
                    
        return count

Details

Runtime: 48 ms, faster than 81.81% of Python3 online submissions forPath Sum III.

Memory Usage: 15.9 MB, less than 15.29% of Python3 online submissions for Path Sum III.

Complexity Analysis

• Time complexity: O(N), where N is a number of nodes. During preorder traversal, each node is visited once.
• Space complexity: up to O(N) to keep the hashmap of prefix sums, where NN is a number of nodes.