Path Sum IV

Problem

If the depth of a tree is smaller than 5, then this tree can be represented by an array of three-digit integers. For each integer in this array:

• The hundreds digit represents the depth d of this node where 1 <= d <= 4.
• The tens digit represents the position p of this node in the level it belongs to where 1 <= p <= 8. The position is the same as that in a full binary tree.
• The units digit represents the value v of this node where 0 <= v <= 9.

Given an array of ascending three-digit integers nums representing a binary tree with a depth smaller than 5, return the sum of all paths from the root towards the leaves.

It is guaranteed that the given array represents a valid connected binary tree.

Examples

Example 1

graph TD;
	C(3) --- E(5) & A(1) 

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

Example 2

graph TD;
	C(3) ~~~ N1:::hidden
	C --- A(1) 
classDef hidden display:none

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

Solution

The problem involves calculating the sum of all root-to-leaf paths in a binary tree represented by an array of three-digit integers. Here's how the representation works:

• The hundreds digit represents the level (depth d) of the node.
• The tens digit represents the position (p) of the node within its level in a full binary tree.
• The units digit represents the value of the node.

The goal is to simulate the tree traversal and compute the sum of all root-leaf paths.

Method 1 - DFS

Here is the approach:

1. Parsing the array:
   • Map each node to its depth, position, and value.
2. Recursive DFS:
   • Treat the nodes as a tree and traverse using DFS. A node is root of a subtree if it has associated child nodes.
   • During traversal, compute the sum of each path by accumulating values along the way.
   • Add to the total sum when a leaf node is reached (no dependent child nodes).
3. Tree node recognition:
   • Children of a node at depth = d and position = p are at depth = d + 1 and positions = 2 * p - 1 (left child) and 2 * p (right child).

Code

Java

class Solution {
    public int pathSum(int[] nums) {
        // Map to store nodes
        Map<Integer, Integer> tree = new HashMap<>();
        for (int num : nums) {
            tree.put(num / 10, num % 10); // key: (depth * 10 + position), value: node value
        }
        final int[] ans = {0}; // Total sum

        // DFS method
        dfs(nums[0] / 10, 0, tree, ans);
        return ans[0];
    }

    private void dfs(int node, int acc, Map<Integer, Integer> tree, int[] ans) {
        if (!tree.containsKey(node)) return; // Node doesn't exist

        acc += tree.get(node); // Accumulate value
        int d = node / 10, p = node % 10; // Extract depth and position
        int left = (d + 1) * 10 + 2 * p - 1; // Left child
        int right = (d + 1) * 10 + 2 * p;   // Right child

        // If leaf node, add to sum
        if (!tree.containsKey(left) && !tree.containsKey(right)) {
            ans[0] += acc;
        } else {
            dfs(left, acc, tree, ans);  // Traverse left
            dfs(right, acc, tree, ans); // Traverse right
        }
    }
}

Python

class Solution:
    def pathSum(self, nums: List[int]) -> int:
        # Map nodes for quick access
        tree = {num // 10: num % 10 for num in nums}  # key: (depth * 10 + position), value: node value
        ans = 0

        # DFS function
        def dfs(node: int, acc: int) -> None:
            nonlocal ans
            if node not in tree:  # If node does not exist
                return

            acc += tree[node]  # Accumulate value
            d, p = divmod(node, 10)  # Get depth and position
            left = (d + 1) * 10 + 2 * p - 1     # Left child
            right = (d + 1) * 10 + 2 * p        # Right child

            # If leaf node, add to the sum
            if left not in tree and right not in tree:
                ans += acc
            else:
                dfs(left, acc)   # Traverse left
                dfs(right, acc)  # Traverse right

        # Start DFS from root (hundreds digit of the smallest number)
        dfs(nums[0] // 10, 0)
        return ans

Complexity

• ⏰ Time complexity: O(n) where n is the size of the input array since each node is visited once.
• 🧺 Space complexity: O(h) where h is the height of the tree (max depth 4) due to the recursion stack.