Problem Description

The Path Sum IV problem on LeetCode provides you with an array nums that represents a binary tree in a special encoded form. Each integer in nums is a three-digit number where:

• The hundreds digit represents the depth of the node (1-indexed).
• The tens digit represents the position of the node in that depth (1-indexed, left to right).
• The units digit represents the value of the node.

The binary tree is constructed such that the root starts at depth 1, position 1. Each node's left child is at the next depth and position pos * 2 - 1, and the right child is at pos * 2.

The task is to compute the sum of all root-to-leaf path sums in the tree. For each root-to-leaf path, sum up the node values along that path, and then sum those totals for all possible root-to-leaf paths.

Constraints:

• Each node is unique in nums.
• There may be at most 15 nodes (since the tree's maximum depth is 4).
• Only root-to-leaf paths are considered.

Thought Process

At first glance, this problem might seem tricky due to the encoded input format. A brute-force approach would be to reconstruct the tree in memory, then traverse it to compute all root-to-leaf path sums.

However, building a full tree structure is unnecessary. Instead, we can map the encoded numbers to their positions, and use this mapping to traverse the tree virtually. For each node, we can recursively check if it has children by looking up their expected encoded keys.

The main challenge is decoding the node information and efficiently checking for children. Using a hash map (dictionary) allows us to quickly check if a child exists, making our traversal efficient.

By shifting from a brute-force "build the tree, then traverse" method to a direct "traverse with a map" approach, we save both time and space.

Solution Approach

• Step 1: Parse the Input
  • For each number in nums, extract the depth, position, and value.
  • Store these in a map: the key is a tuple (depth, position), the value is the node's value.
• Step 2: Depth-First Search (DFS)
  • Start from the root node (depth=1, position=1).
  • At each node, compute the current path sum.
  • Compute the positions of the left and right children according to the encoding rules.
  • If a child exists in the map, recursively traverse it.
  • If a node is a leaf (no children), add the current path sum to the result.
• Step 3: Accumulate the Result
  • Keep a running total of all root-to-leaf path sums.
  • Return the total after the traversal completes.

Using a hash map for node lookup ensures O(1) access to any node, and recursion allows us to naturally process all paths from root to leaves.

Example Walkthrough

Let's use the input nums = [113, 215, 221] as an example.

• 113: depth=1, pos=1, value=3 (root)
• 215: depth=2, pos=1, value=5 (left child of root)
• 221: depth=2, pos=2, value=1 (right child of root)

The tree looks like:

• Root (3)
  • Left child (5)
  • Right child (1)

There are two root-to-leaf paths:

• 3 → 5: sum is 8
• 3 → 1: sum is 4

During traversal:

• Start at (1,1): value=3, pathSum=3
• Go to (2,1): value=5, pathSum=8 (leaf, add 8)
• Go to (2,2): value=1, pathSum=4 (leaf, add 4)

Time and Space Complexity

• Brute-force approach:
  • Building a full tree: O(N)
  • Traversing all paths: O(N) (since the tree is small and each node is visited once)
  • Space: O(N) for the tree structure
• Optimized approach (mapping + DFS):
  • Building the map: O(N)
  • DFS traversal: O(N) (each node visited once)
  • Space: O(N) for the map and call stack (max depth 4)

Since N ≤ 15, both approaches are efficient, but the optimized approach is simpler and avoids unnecessary structures.

Summary

The Path Sum IV problem is a great example of how understanding the input encoding and leveraging data structures like hash maps can lead to a clean, efficient solution. By mapping node positions and values, and using recursive DFS, we can compute all root-to-leaf path sums without explicitly building a tree. This approach is both elegant and practical, especially when working with compact or encoded data representations.

Code Implementation

class Solution:
    def pathSum(self, nums):
        tree = {}
        for num in nums:
            d, p, v = num // 100, (num // 10) % 10, num % 10
            tree[(d, p)] = v

        self.total = 0

        def dfs(depth, pos, path_sum):
            key = (depth, pos)
            if key not in tree:
                return
            curr_sum = path_sum + tree[key]
            left = (depth + 1, pos * 2 - 1)
            right = (depth + 1, pos * 2)
            if left not in tree and right not in tree:
                self.total += curr_sum
                return
            dfs(depth + 1, pos * 2 - 1, curr_sum)
            dfs(depth + 1, pos * 2, curr_sum)

        dfs(1, 1, 0)
        return self.total
    

class Solution {
public:
    int pathSum(vector<int>& nums) {
        unordered_map<int, int> tree;
        for (int num : nums) {
            int d = num / 100;
            int p = (num / 10) % 10;
            int v = num % 10;
            tree[d * 10 + p] = v;
        }
        int total = 0;
        function<void(int, int, int)> dfs = [&](int depth, int pos, int sum) {
            int key = depth * 10 + pos;
            if (tree.find(key) == tree.end()) return;
            int curr_sum = sum + tree[key];
            int left = (depth + 1) * 10 + (pos * 2 - 1);
            int right = (depth + 1) * 10 + (pos * 2);
            if (tree.find(left) == tree.end() && tree.find(right) == tree.end()) {
                total += curr_sum;
                return;
            }
            dfs(depth + 1, pos * 2 - 1, curr_sum);
            dfs(depth + 1, pos * 2, curr_sum);
        };
        dfs(1, 1, 0);
        return total;
    }
};
    

class Solution {
    private int total = 0;
    private Map<String, Integer> tree = new HashMap<>();

    public int pathSum(int[] nums) {
        for (int num : nums) {
            int d = num / 100;
            int p = (num / 10) % 10;
            int v = num % 10;
            tree.put(d + "," + p, v);
        }
        dfs(1, 1, 0);
        return total;
    }

    private void dfs(int depth, int pos, int sum) {
        String key = depth + "," + pos;
        if (!tree.containsKey(key)) return;
        int currSum = sum + tree.get(key);
        String left = (depth + 1) + "," + (pos * 2 - 1);
        String right = (depth + 1) + "," + (pos * 2);
        if (!tree.containsKey(left) && !tree.containsKey(right)) {
            total += currSum;
            return;
        }
        dfs(depth + 1, pos * 2 - 1, currSum);
        dfs(depth + 1, pos * 2, currSum);
    }
}
    

var pathSum = function(nums) {
    const tree = new Map();
    for (let num of nums) {
        const d = Math.floor(num / 100);
        const p = Math.floor((num / 10) % 10);
        const v = num % 10;
        tree.set(d + ',' + p, v);
    }
    let total = 0;
    function dfs(depth, pos, sum) {
        const key = depth + ',' + pos;
        if (!tree.has(key)) return;
        const currSum = sum + tree.get(key);
        const left = (depth + 1) + ',' + (pos * 2 - 1);
        const right = (depth + 1) + ',' + (pos * 2);
        if (!tree.has(left) && !tree.has(right)) {
            total += currSum;
            return;
        }
        dfs(depth + 1, pos * 2 - 1, currSum);
        dfs(depth + 1, pos * 2, currSum);
    }
    dfs(1, 1, 0);
    return total;
};