Trees & Hashmap — Path Sum IV

If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers.

For each integer in this list:

1. The hundreds digit represents the depth D of this node, 1 <= D <= 4.
2. The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree.
3. The units digit represents the value V of this node, 0 <= V <= 9.

Given a list of ascending three-digits integers representing a binary tree with the depth smaller than 5, you need to return the sum of all paths from the root towards the leaves.

It’s guaranteed that the given list represents a valid connected binary tree.

Example 1:

Input: [113, 215, 221]
Output: 12
Explanation: 
The tree that the list represents is:
    3
   / \
  5   1
The path sum is (3 + 5) + (3 + 1) = 12.

Example 2:

Input: [113, 221]
Output: 4
Explanation: 
The tree that the list represents is: 
    3
     \
      1
The path sum is (3 + 1) = 4.

SOlution:

I use a simple approach.

If we look at only the first two digits i.e. depth and level, we can see a pattern. I plan to exploit the pattern using a hashmap.

We can compute the depth of the child from the parents depth [ child_depth = parent_depth + 1]. We can also compute the levels of the children [ left_level = parent_level * 2 -1] and [ right_level = parent_level * 2 ]. So the location of the children is [child_depth * 10 + [left/right]_levels]

Lets use a hashmap to store the values of all the children and then pass the roots information to the children. By passing the information, we add the parents sum to the child’s values.

If a node has none of its child in the map, we simply add the number to the final result.

Code:

class Solution:
    def pathSum(self, nums: List[int]) -> int:
        result = 0
        hmap = {}
        
        for x in nums:
            value = x % 10
            depth_level = x // 10
            hmap[depth_level] = value
        
        for x in nums:
            parent = x // 10
            plevel = parent % 10
            pdepth = parent - plevel
            
            child1_level = plevel * 2 - 1
            #child2_level = plevel * 2
            child2_level = child1_level + 1
            child1 = pdepth + 10 + child1_level
            if child1 in hmap:
                hmap[child1] += hmap[parent]
            
            child2 = child1 + 1
            if child2 in hmap:
                hmap[child2] += hmap[parent]
            
            if child1 not in hmap and child2 not in hmap:
                result += hmap[parent]
                
        return result

Other solutions:

class Solution(object):
    def pathSum(self, nums):
        self.ans = 0
        
        # map to hold the values
        hmap = {x // 10: x % 10 for x in nums}
        
        def preorder_dfs(node, running_sum = 0):
            if node not in hmap:
                return
            
            # update the running sum
            running_sum += hmap[node]
            
            # get the depth and position of children.
            depth, pos = divmod(node, 10)
            left = (depth + 1) * 10 + 2 * pos - 1
            right = left + 1
            if left not in hmap and right not in hmap:
                self.ans += running_sum
            else:
                dfs(left, running_sum)
                dfs(right, running_sum)
        dfs(nums[0] / 10)
        return self.ans

Runtime: 28 ms, faster than 86.92% of Python3 online submissions forPath Sum IV.

Memory Usage: 14.2 MB, less than 71.96% of Python3 online submissions for Path Sum IV.

Complexity Analysis

• Time and Space Complexity: O(N)O(N). The analysis is the same as in Approach #1.