Vultr DocsLatest Content

Path Sum IV

Updated on 01 July, 2025
Path Sum IV header image

Problem Statement

In this problem, you are given an array of three-digit integers known as nums, where each integer uniquely represents a node in a binary tree with a maximum depth of less than 5. The structure of each three-digit integer is as follows:

  • The first digit (hundreds digit) indicates the depth d of the node within the tree, adhering to the constraint 1 <= d <= 4.
  • The second digit (tens digit) specifies the position p of the node on its particular level. This is based on the node's position within a full binary tree, where the possible positions range from 1 to 8.
  • The third digit (units digit) represents the actual value v of that node, ranging from 0 to 9.

You need to determine the sum of all the path values from the root of the tree to its leaves. Each path's value is calculated from the sequence of nodes' values that you traverse from the root to a leaf node. The array you are given is guaranteed to represent a valid binary tree and is sorted in ascending order based on the depth and position of the nodes.

Examples

Example 1

Input:

nums = [113,215,221]

Output:

12

Explanation:

The tree that the list represents is shown.

Example 2

Input:

nums = [113,221]

Output:

4

Explanation:

The tree that the list represents is shown.

Constraints

  • 1 <= nums.length <= 15
  • 110 <= nums[i] <= 489
  • nums represents a valid binary tree with depth less than 5.
  • nums is sorted in ascending order.

Approach and Intuition

  1. Understanding the Tree Structure:

    • The information about node depth, position, and value are all encoded into a three-digit number which facilitates the approach to reconstructing the tree dynamically if needed.

  2. Reconstruction of Tree:

    • Create a node structure that can maintain information regarding its value and its child nodes.
    • Parse through the nums array, decode each number into its depth, positional, and value components, and appropriately place it within a virtual binary tree structure.

  3. Calculating Sum of All Path Values:

    • Begin at the root node and explore all possible paths to leaf nodes.
    • As each path from the root to a leaf is traversed, keep a running sum of node values until the leaf is reached, then add the final sum to a total sum count.
    • Use a recursive depth-first search (DFS) approach to explore each path, which is a common method for this type of tree traversal problem.

  4. Return the Total Sum:

    • After all paths have been explored and their sums calculated, the final step is to return the accumulated sum of all path values from the root to the leaves.

Considering the constraints provided, such as the maximum possible number of nodes is 15 and the depth is less than 5, the approach described should be computationally feasible.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    int calculatePathSum(vector<int>& numbers) {
        unordered_map<int, int> nodeValues;
        for (int num : numbers) {
            int key = num / 10;
            int value = num % 10;
            nodeValues[key] = value;
        }
    
        queue<pair<int, int>> nodesQueue;
        int sumResult = 0;
    
        int baseNode = numbers[0] / 10;
        nodesQueue.push({baseNode, nodeValues[baseNode]});
    
        while (!nodesQueue.empty()) {
            auto [nodeKey, accumulatedSum] = nodesQueue.front();
            nodesQueue.pop();
    
            int level = nodeKey / 10;
            int pos = nodeKey % 10;
    
            int leftChildKey = (level + 1) * 10 + pos * 2 - 1;
            int rightChildKey = (level + 1) * 10 + pos * 2;
    
            if (!nodeValues.count(leftChildKey) && !nodeValues.count(rightChildKey)) {
                sumResult += accumulatedSum;
            }
    
            if (nodeValues.count(leftChildKey)) {
                nodesQueue.push({leftChildKey, accumulatedSum + nodeValues[leftChildKey]});
            }
    
            if (nodeValues.count(rightChildKey)) {
                nodesQueue.push({rightChildKey, accumulatedSum + nodeValues[rightChildKey]});
            }
        }
    
        return sumResult;
    }
};

The provided solution in C++ focuses on calculating the sum of all root-to-leaf paths in a tree represented by a flattened data structure. Here is a concise breakdown of the process encapsulated in the calculatePathSum function:

  1. Initialize an unordered map nodeValues to store the value of each node using a unique key derived from the node's position in the tree.

  2. Use a loop to populate nodeValues from the numbers vector. Each number represents a node, where the integer division of the number by 10 gives the node position (key), and the remainder gives the node value.

  3. Create a queue to manage the nodes as they are processed. Each element in the queue holds a pair consisting of the node key and the cumulative sum of values from the root to the current node.

  4. Initialize the sum accumulator sumResult to zero.

  5. Start with the root node, fetched from the first number in numbers, and push it onto the queue with its value.

  6. Use a while loop to process each node in the queue:

    • Dequeue the front node and determine its level and position within its level.
    • Compute the keys of the potential left and right children based on the current node's key.
    • Check if the dequeued node is a leaf (has no children):
      • If true, add the accumulated sum to sumResult.
    • If the node has a left child, enqueue this child with its accumulated sum.
    • If the node has a right child, do likewise.

  7. The loop continues until the queue is empty, indicating all possible paths have been processed.

  8. Return sumResult, which now contains the sum of all root-to-leaf paths.

This approach efficiently calculates the total path sum using breadth-first search (BFS) by leveraging a queue for node processing and a map for quick lookup of node values.

java 
class Solution {
    
    public int sumOfPaths(int[] treeNodes) {
        // Storing node values with coordinate keys in hashmap.
        Map<Integer, Integer> coordMap = new HashMap<>();
        for (int node : treeNodes) {
            int key = node / 10;
            int value = node % 10;
            coordMap.put(key, value);
        }
    
        // Queue for BFS algorithm initialization with the root node.
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        int sum = 0;
    
        int rootKey = treeNodes[0] / 10;
        queue.offer(new Pair<Integer, Integer>(rootKey, coordMap.get(rootKey)));
    
        while (!queue.isEmpty()) {
            Pair<Integer, Integer> currentPair = queue.poll();
            int currentNode = currentPair.getKey();
            int currentPathSum = currentPair.getValue();
            int level = currentNode / 10;
            int pos = currentNode % 10;
    
            // Calculating coordinates of left and right children.
            int leftChild = (level + 1) * 10 + pos * 2 - 1;
            int rightChild = (level + 1) * 10 + pos * 2;
    
            // Check if node is leaf by absence of both children and add to sum if true.
            if (!coordMap.containsKey(leftChild) && !coordMap.containsKey(rightChild)) {
                sum += currentPathSum;
            }
    
            // Add left child to queue if present.
            if (coordMap.containsKey(leftChild)) {
                queue.offer(new Pair<Integer, Integer>(leftChild, currentPathSum + coordMap.get(leftChild)));
            }
    
            // Add right child to queue if present.
            if (coordMap.containsKey(rightChild)) {
                queue.offer(new Pair<Integer, Integer>(rightChild, currentPathSum + coordMap.get(rightChild)));
            }
        }
    
        return sum;
    }
}

This Java solution involves finding the sum of all root-to-leaf paths in a tree, where the tree is represented as an array of integers in a unique format. Each integer in the array combines the node's position and its value, which the solution decodes using modulo and integer division operations.

Here is how the solution works:

  1. Initiate a HashMap called coordMap to store the value of each tree node with a coordinate key derived from the integer representation.
  2. Convert the initial array of tree nodes (treeNodes) such that each element is parsed into a coordinate and its corresponding value, which are then stored in coordMap.
  3. Use a queue to perform a Breadth-First Search (BFS). Each node in the queue is processed to determine if it is a leaf node. If it is, the path sum to that node is added to the total sum.
  4. For each non-leaf node, calculate the coordinates of possible left and right children and check if they exist in coordMap. If they do, add the child's value to the current path sum and enqueue the child for further exploration.
  5. Repeat until there are no more nodes in the queue, at which point sum contains the sum of all root-to-leaf paths.

This approach cleverly uses a combination of BFS for traversal and a HashMap for rapid node existence checks and value access, ensuring efficient calculations even for relatively large tree structures. The end result is an accumulation of the values from all valid root-to-leaf paths.

python 
class Solution:
    def calculatePathSum(self, tree_numbers: List[int]) -> int:
        node_values = {}  # Keep node values indexed by their coordinates.
    
        # Populate the hashmap with the tree nodes
        for num in tree_numbers:
            coord = num // 10
            val = num % 10
            node_values[coord] = val
    
        global_sum = 0  # Initialize sum of path values
        queue = [(tree_numbers[0] // 10, node_values[tree_numbers[0] // 10])]  # Start BFS from the root node
    
        # Process all nodes in the BFS queue until it's empty
        while queue:
            node_coord, summed_value = queue.pop(0)  # Get the current node from the queue
            lvl = node_coord // 10
            pos = node_coord % 10
    
            left_child_coord = (lvl + 1) * 10 + pos * 2 - 1
            right_child_coord = (lvl + 1) * 10 + pos * 2
    
            # Check if the node is a leaf node add its summed value to the global sum
            if not (left_child_coord in node_values or right_child_coord in node_values):
                global_sum += summed_value
    
            # Queue the left child
            if left_child_coord in node_values:
                queue.append((left_child_coord, summed_value + node_values[left_child_coord]))
                
            # Queue the right child
            if right_child_coord in node_values:
                queue.append((right_child_coord, summed_value + node_values[right_child_coord]))
    
        return global_sum  # Return the sum of all paths from the root to the leaves

In solving the "Path Sum IV" problem in Python, the following solution leverages the Breadth-First Search (BFS) approach to compute the sum of all root-to-leaf paths in a tree defined by node values encoded in a single list, tree_numbers. Here's a breakdown of how the solution works:

  • First, the code creates a dictionary, node_values, mapping each node's position to its value. This is necessary because nodes in tree_numbers are encoded such that the integer's tens and hundreds place represents the node's coordinates (level and position), and the units place indicates the node's value.

  • It initializes global_sum to accumulate the sum of values on all paths from the root to each leaf and uses a queue for BFS, starting at the tree’s root.

  • During the BFS, it processes nodes in the queue one by one:

    • Decodes the node's level and position from its coordinates.
    • Determines coordinates for potential left and right child nodes.
    • If a node is found to be a leaf (neither child exists in the mapping), its accumulated path sum (summed_value) gets added to global_sum.
    • If child nodes exist, they are added to the queue with updated path sums.

  • This iteration continues until the queue is empty, meaning all paths have been evaluated.

  • Finally, the function returns global_sum, which by the end of the process holds the total sum of all sums from the root node down to every leaf node.

This method provides an efficient way to traverse and calculate required sums in a tree structure defined in a non-traditional way using a single list of integers.

Comments

No comments yet.