666. Path Sum IV

MediumTreeDepth-First SearchArrayHash TableBinary Tree

Problem Description

In this problem, we're given a binary tree with a depth smaller than 5, which is represented as an array of three-digit integers. The representation of the tree using integers has specific rules:

The first digit (the hundreds) indicates the depth of the binary tree node (d), which can range from 1 to 4.
The second digit (the tens) indicates the position of the node (p) within its level, similar to its position in a full binary tree, ranging from 1 to 8.
The third digit (the units) is a value of the node (v), which can be between 0 and 9.

The task is to find the sum of all root-to-leaf paths' values. The array is given in ascending order, and it's ensured that it represents a valid connected binary tree.

A path is defined as a sequence of nodes from the root of the tree to any leaf node, and the path sum is the sum of values of nodes along that particular path.

Flowchart Walkthrough

Let's analyze the problem using the Flowchart. Here's a step-by-step walkthrough for LeetCode 666. Path Sum IV:

Is it a graph?
- Yes: The problem presents a structure that can be interpreted as a graph, where each node represents a position in a tree structure encoded as an array.
Is it a tree?
- Yes: The problem specifically involves computing values in a tree structure where nodes are connected in a parent-child relationship.
Is it a tree so use DFS?
- Yes: Since it is a tree, the Depth-First Search (DFS) pattern fits perfectly to traverse through each path from root to leaves, calculating the sum as per the conditions given.

Conclusion: The flowchart suggests using DFS for effectively solving the problem as it involves processing a tree structure and computing the sums of all paths from root to leaves.

Intuition

To solve this problem, we can use Depth-First Search (DFS), a standard tree traversal algorithm that goes as deep as possible in one direction before backtracking. The goal is to traverse the tree from the root to each leaf and accumulate the values of the nodes along these paths.

Here's the intuition behind the solution approach:

Represent the Tree Structure: Since the tree is given as a sequence of integers, we first need to map this representation to one that we can use for DFS. The mapping is based on depth and position. We can use a dictionary to store the nodes, where each key represents the depth and position (without the value digit), and the corresponding value is the node's value. This will help us find a node's children.
Implement DFS: We'll define a recursive function that will take a node (represented as an integer with depth and position information) and a running total sum (initially set to 0). The function will perform the following actions:
- Check if the current node is a leaf (has no children) and, if so, add the running total sum to the global answer.
- Otherwise, call the function recursively for the left and right children, increasing the depth and calculating the position for each child based on the rules.
- Accumulate the node's value to the running total sum as we traverse down the tree.
Handle Edge Cases: We're guaranteed that the array represents a valid tree. However, we do need to ensure that we're checking for the existence of children nodes using the mapping before trying to traverse them.
Compute the Result: By running DFS starting from the root, we can compute the sum of all the root-to-leaf paths. The root is represented as 11 since the depth is 1 and position is 1.

This way, we can explore all paths, sum their values, and obtain the total sum required by the problem.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

To implement the solution to this problem, a few critical components are used:

Dictionary Representation: A dictionary, denoted as mp in the code, is created to efficiently store and access nodes using their hundreds and tens digits as keys (representing depth and position) and their units digit as the value. The dictionary comprehension {num // 10: num % 10 for num in nums} achieves this by dividing each number by 10 (to remove the value digit) and then mapping this to the remainder (the value digit).
Depth-First Search (DFS): The DFS is implemented through a recursive function, dfs(node, t), where node is the current node being visited and t is the running total sum of values on the path from the root to the current node.
Node Representation and Child Calculation: Each node is represented as a two-digit number where the first digit correlates to the depth and the second digit corresponds to the position. To find children of a node at depth d and position p, we calculate the left child as (d + 1) * 10 + (p * 2) - 1 and the right child as l + 1. The multiplication and addition here are based on the properties of a binary tree, where each level has twice as many nodes as the previous, and positions start on the leftmost side at 1 and increase to the right.
Leaf Check and Sum Accumulation: The function checks to see if the current node is a leaf, meaning it has no children in the mapping mp. If it's a leaf, the current path's sum (which includes the current node's value) is added to a global variable ans, which accumulates the total sum of all paths.
Recursion: The DFS function is called recursively on the node's children, passing the updated total sum t combined with the current node's value. This is done with dfs(l, t) and dfs(r, t) for the left and right child respectively.
Global Variable: Since Python doesn't support passing primitives by reference, and updating a local variable won't affect its value outside the current scope, a nonlocal declaration (nonlocal ans) is used to modify the ans variable, which holds the total path sum, within the recursive function.

Finally, the DFS is kicked off from the root of the tree, which always has a depth and position of 1 (hence node 11), and an initial total path sum of 0. The accumulated sum of all paths, stored in ans, is returned as the result after completing all recursions.

The efficiency of this approach lies in its use of recursion and the dictionary, which allows constant-time lookups for the existence of child nodes, as well as the ability to directly calculate children's identifiers from a given node's identifier without needing to construct the actual tree structure.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a simple example to illustrate the solution approach.

Suppose we're given the following representation of a binary tree using an array of three-digit integers: [111, 121, 122, 131, 132]. Here's what each number means:

111: Root node with a value of 1, at depth 1 and position 1.
121: Left child of the root with a value of 1, at depth 2 and position 1.
122: Right child of the root with a value of 2, at depth 2 and position 2.
131: Left child of node 121 with a value of 1, at depth 3 and position 1 (this is a leaf node).
132: Right child of node 121 with a value of 2, at depth 3 and position 2 (this is a leaf node).

Now let's map this representation to one suitable for depth-first search:

Dictionary Representation:

We create a dictionary mp like so:

{
  11: 1,  // Root node
  12: 1,  // Left child of root
  13: 2,  // Right child of root
  13: 1,  // Left child of node 12
  14: 2   // Right child of node 12
}

This maps the depth-position identifier to the node's value.

Implementing DFS:
- We define a recursive function dfs(node, t).
- Initially, we call dfs(11, 0) because our root is 111, and our initial total path sum is 0.
Traversing the Tree:
- Starting with node 11, we check for its children, which are, in theory, 121 (left child) and 122 (right child).
- For the left child 121, we calculate its identifier as 12 (by stripping away the value digit), which is present in mp. Therefore, we call dfs(12, 1) (1 being the current total sum plus root's value).
- For the right child 122, we also calculate its identifier as 13 and since it's in mp, we call dfs(13, 1).
Summing Path Values:
- We then traverse to node 121 (12 in mp). We check for children 131 and 132 similarly, ending up calling dfs(13, 2) and dfs(14, 2) respectively since 12 + 1 = 2.
- Both are leaves, so we add their sums (2 + 1) and (2 + 2) to a global variable ans.
Calculating Results:
- By recursing through both left and right children for all nodes, we add all the root-to-leaf paths to ans.
- The paths we have taken are: 111 -> 121 -> 131 and 111 -> 121 -> 132.
- This results in sums of 1 + 1 + 1 = 3 and 1 + 1 + 2 = 4 respectively.
- Our ans turns out to be 3 + 4 = 7.

Finally, ans contains the sum of the values of all root-to-leaf paths which in our case is 7. This is returned as the result of our problem.

Solution Implementation

1from typing import List
2
3class Solution:
4    def pathSum(self, nums: List[int]) -> int:
5        # Helper function for depth-first search from a given node with cumulative total `total`
6        def dfs(node, total):
7            # If the current node is not in the tree, stop the recursion
8            if node not in tree_map:
9                return
10            # Add the current node's value to the running total
11            total += tree_map[node]
12            depth, pos = divmod(node, 10) # Split the node code into depth and positional information
13            # Calculate the node code for the left and right children
14            left_child = (depth + 1) * 10 + (pos * 2) - 1
15            right_child = left_child + 1
16            # If both children are absent, add the current total to the global 'answer'
17            if left_child not in tree_map and right_child not in tree_map:
18                nonlocal answer
19                answer += total
20                return
21            # Recurse on the left and right children
22            dfs(left_child, total)
23            dfs(right_child, total)
24
25        # Initialize the answer variable to accumulate the total path sums
26        answer = 0
27        # Create a mapping from node codes (depth and position) to values using list comprehension
28        tree_map = {num // 10: num % 10 for num in nums}
29        # Start the DFS traversal from the root node (code 11) with an initial total of 0
30        dfs(11, 0)
31        # Return the accumulated total path sums
32        return answer
33

1class Solution {
2    private int totalPathSum; // Use a more descriptive name for the variable 'ans'.
3    private Map<Integer, Integer> valueMap; // Rename 'mp' to 'valueMap' for clarity.
4
5    // Computes the sum of all paths in the tree.
6    public int pathSum(int[] nums) {
7        totalPathSum = 0;
8        valueMap = new HashMap<>(nums.length);
9      
10        // Store each value in a map with its key as {node level}{node position}
11        for (int num : nums) {
12            // Dividing by 10 gives us the {node level}{node position}, modulo 10 gives us the value at that node
13            valueMap.put(num / 10, num % 10);
14        }
15      
16        // Start DFS from the root node, which is always 11
17        dfs(11, 0);
18        return totalPathSum;
19    }
20
21    // Performs a depth-first search to calculate all path sums.
22    private void dfs(int node, int currentSum) {
23        // If the node does not exist, return
24        if (!valueMap.containsKey(node)) {
25            return;
26        }
27
28        // Add the value of the current node to the running sum
29        currentSum += valueMap.get(node);
30
31        // Calculate level and position for the current node
32        int level = node / 10;
33        int position = node % 10;
34
35        // Calculate the node values for the left and right children
36        int leftChild = (level + 1) * 10 + (position * 2) - 1;
37        int rightChild = leftChild + 1;
38
39        // If the node is a leaf node, add the running sum to the total path sum
40        if (!valueMap.containsKey(leftChild) && !valueMap.containsKey(rightChild)) {
41            totalPathSum += currentSum;
42            return;
43        }
44
45        // Continue DFS on the left and right children
46        dfs(leftChild, currentSum);
47        dfs(rightChild, currentSum);
48    }
49}
50

1class Solution {
2public:
3    int totalPathSum; // Holds the total sum of path values
4    unordered_map<int, int> nodesMap; // Maps the node id to its value
5
6    // Main function to calculate the sum of the path values.
7    int pathSum(vector<int>& nums) {
8        totalPathSum = 0; // Initialize total path sum
9        nodesMap.clear(); // Clear the map before computation
10
11        // Populate the map with node values. Node id as key and node value as value.
12        for (int num : nums) {
13            nodesMap[num / 10] = num % 10;
14        }
15
16        // Start depth-first search at the root node, which is id 11.
17        dfs(11, 0);
18      
19        // Return the computed total path sum.
20        return totalPathSum;
21    }
22
23    // Recursive depth-first search function to compute path sums.
24    void dfs(int nodeId, int sum) {
25        // Check if node id is not present, and return if it's not.
26        if (!nodesMap.count(nodeId)) {
27            return;
28        }
29
30        sum += nodesMap[nodeId]; // Add the node's value to the running sum.
31
32        // Compute the current node's depth and position.
33        int depth = nodeId / 10;
34        int position = nodeId % 10;
35
36        // Calculate left and right children's ids.
37        int leftChildId = (depth + 1) * 10 + (position * 2) - 1;
38        int rightChildId = leftChildId + 1;
39
40        // Check if the node is a leaf node (i.e., it doesn't have any children)
41        if (!nodesMap.count(leftChildId) && !nodesMap.count(rightChildId)) {
42            totalPathSum += sum; // Add the sum to the total path sum.
43            return;
44        }
45
46        // Recursive calls for left and right children.
47        dfs(leftChildId, sum);
48        dfs(rightChildId, sum);
49    }
50};
51

1// Global variable to hold the total sum of path values.
2let totalPathSum: number = 0;
3
4// Global map to associate node ids with their values.
5let nodesMap = new Map<number, number>();
6
7/**
8 * Function to calculate the sum of the path values for a binary tree represented by an array.
9 * @param nums An array representing a binary tree where each element is composed of 3 digits.
10 */
11function pathSum(nums: number[]): number {
12    totalPathSum = 0;   // Initialize the total path sum.
13    nodesMap.clear();   // Clear the map before starting the computation.
14
15    // Populate the map with node values where key is node id and value is node value.
16    nums.forEach(num => {
17        nodesMap.set(Math.floor(num / 10), num % 10);
18    });
19
20    // Start depth-first search at the root node which has id 11.
21    dfs(11, 0);
22
23    // Return the total sum of path values computed.
24    return totalPathSum;
25}
26
27/**
28 * Recursive depth-first search function to compute path sums.
29 * @param nodeId The id of the current node.
30 * @param sum The sum of values along the current path.
31 */
32function dfs(nodeId: number, sum: number): void {
33    // Check if the node id exists in the map. If not, return immediately.
34    if (!nodesMap.has(nodeId)) {
35        return;
36    }
37
38    // Add the current node's value to the running sum.
39    sum += nodesMap.get(nodeId) || 0;
40
41    // Calculate the depth and position for the current node.
42    const depth: number = Math.floor(nodeId / 10);
43    const position: number = nodeId % 10;
44
45    // Calculate the ids for the left and right children of the current node.
46    const leftChildId: number = (depth + 1) * 10 + (position * 2) - 1;
47    const rightChildId: number = leftChildId + 1;
48
49    // Check if the current node is a leaf node (does not have any children).
50    if (!nodesMap.has(leftChildId) && !nodesMap.has(rightChildId)) {
51        // Since it's a leaf, add the path sum to the total.
52        totalPathSum += sum;
53        return;
54    }
55
56    // Recursively call dfs for the left and right children if they exist.
57    dfs(leftChildId, sum);
58    dfs(rightChildId, sum);
59}
60

Time and Space Complexity

The provided code defines a method pathSum which computes the sum of all paths in a binary tree represented in a compact array form where an integer xyz represents a node at depth x (1-indexed), position y (1-indexed) within its level, with value z. To calculate the sum of all root-to-leaf paths, the code uses a Depth-First Search (DFS) algorithm.

Time Complexity

The time complexity of the function is O(N), where N is the number of elements in the nums array. This is because:

Each element in the array is visited exactly once to populate the mp dictionary.
The dfs function is called recursively to explore all possible paths from the root to the leaves. In the worst case, the tree is a full binary tree, and dfs will be called exactly 2^h - 1 times, where h is the height of the tree. Since the nums array can at most represent a binary tree with a height where 2^h - 1 is equal to the length of nums, the dfs call does not increase the complexity beyond O(N).

Space Complexity

The space complexity of the function is O(H), where H is the height of the binary tree represented by the nums array. This accounts for:

The space used by the mp dictionary, which is equal to the number of elements in nums, i.e., O(N).
The maximum depth of the recursion stack, which is equal to the height of the tree H, i.e., O(H).
Since N can represent a full binary tree, in the worst case, H could be O(logN) because N = 2^H - 1 in a full binary tree.

Considering the most constraining factor, the overall space complexity is O(H). In the context of this problem, since the depth of the tree is limited (in practical scenarios by the binary tree representation), the space complexity due to the call stack may also be considered O(1) as a constant factor, depending on the constraints of the problem. However, without specific constraints given, we stick with O(H).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: