Path Sum IV solution and explanation
4 more videos on this problem
Leetcode 666 path sum 4DayDay-UpUp · 11:55 · 641 views
666. Path Sum IV (Leetcode Medium)Programming Live with Larry · 18:15 · 398 views
666. Path Sum IV - Week 5/5 Leetcode August ChallengeProgramming Live with Larry · 14:29 · 269 views
Leetcode #666: Path Sum IVJack Chen · 3:34 · 239 views
LeetCode 666: Path Sum IVAlitaCode · 30:05 · 25 views
The problem
If the depth of a tree is smaller than 5, then this tree can be represented by an array of three-digit integers. You are given an ascending array nums consisting of three-digit integers representing a binary tree with a depth smaller than 5, where for each integer:
- The hundreds digit represents the depth
dof this node, where1 <= d <= 4. - The tens digit represents the position
pof this node within its level, where1 <= p <= 8, corresponding to its position in a full binary tree. - The units digit represents the value
vof this node, where0 <= v <= 9.
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.
Example 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:
Input: nums = [113,221]
Output: 4
Explanation:
The tree that the list represents is shown.
The path sum is (3 + 1) = 4.
Constraints:
1 <= nums.length <= 15110 <= nums[i] <= 489numsrepresents a valid binary tree with depth less than5.numsis sorted in ascending order.
Approach overview
Problem Overview: The input represents a binary tree using three-digit integers where the hundreds digit is the depth, the tens digit is the position within that level, and the units digit is the node value. Your task is to reconstruct the structure logically and compute the total of all root‑to‑leaf path sums.
Approach 1: Build the Binary Tree then DFS (O(n) time, O(n) space)
A straightforward method is to explicitly build the tree structure first. Parse each number to extract depth, position, and value, then map each node to its parent using the rule that a node at (d, p) has a parent at (d-1, (p+1)//2). Once the structure is built, run a standard Depth-First Search from the root, accumulating path sums until reaching leaf nodes. Each leaf contributes its path total to the final answer. This approach mirrors how you normally solve path sum problems on a Binary Tree, making it easy to reason about during implementation.
Approach 2: Hash Map + Implicit DFS (O(n) time, O(n) space)
A more efficient approach avoids building the full tree. Store each node in a Hash Table using a key like depth * 10 + position. Then run DFS starting from the root (depth 1, position 1). For each node, compute the keys of its potential children: left child at (d+1, 2p-1) and right child at (d+1, 2p). If neither child exists in the map, the node is a leaf and the current path sum gets added to the result. Otherwise, continue DFS with the updated sum. This method leverages the encoded structure directly and avoids explicit node objects.
The key insight is that the position encoding uniquely determines parent‑child relationships. Because each node can be found with a constant‑time hash lookup, the traversal runs in linear time relative to the number of encoded nodes.
Recommended for interviews: The hash map + implicit DFS approach. It demonstrates that you understand how the positional encoding works and can reconstruct relationships without building a full tree. Mentioning the explicit tree construction approach first can show baseline understanding, but the optimized DFS with hash lookups shows stronger problem‑solving ability.
Solution
class Solution:
def pathSum(self, nums: List[int]) -> int:
def dfs(node, t):
if node not in mp:
return
t += mp[node]
d, p = divmod(node, 10)
l = (d + 1) * 10 + (p * 2) - 1
r = l + 1
nonlocal ans
if l not in mp and r not in mp:
ans += t
return
dfs(l, t)
dfs(r, t)
ans = 0
mp = {num // 10: num % 10 for num in nums}
dfs(11, 0)
return ansclass Solution {
private int ans;
private Map<Integer, Integer> mp;
public int pathSum(int[] nums) {
ans = 0;
mp = new HashMap<>(nums.length);
for (int num : nums) {
mp.put(num / 10, num % 10);
}
dfs(11, 0);
return ans;
}
private void dfs(int node, int t) {
if (!mp.containsKey(node)) {
return;
}
t += mp.get(node);
int d = node / 10, p = node % 10;
int l = (d + 1) * 10 + (p * 2) - 1;
int r = l + 1;
if (!mp.containsKey(l) && !mp.containsKey(r)) {
ans += t;
return;
}
dfs(l, t);
dfs(r, t);
}
}class Solution {
public:
int ans;
unordered_map<int, int> mp;
int pathSum(vector<int>& nums) {
ans = 0;
mp.clear();
for (int num : nums) mp[num / 10] = num % 10;
dfs(11, 0);
return ans;
}
void dfs(int node, int t) {
if (!mp.count(node)) return;
t += mp[node];
int d = node / 10, p = node % 10;
int l = (d + 1) * 10 + (p * 2) - 1;
int r = l + 1;
if (!mp.count(l) && !mp.count(r)) {
ans += t;
return;
}
dfs(l, t);
dfs(r, t);
}
};func pathSum(nums []int) int {
ans := 0
mp := make(map[int]int)
for _, num := range nums {
mp[num/10] = num % 10
}
var dfs func(node, t int)
dfs = func(node, t int) {
if v, ok := mp[node]; ok {
t += v
d, p := node/10, node%10
l := (d+1)*10 + (p * 2) - 1
r := l + 1
if _, ok1 := mp[l]; !ok1 {
if _, ok2 := mp[r]; !ok2 {
ans += t
return
}
}
dfs(l, t)
dfs(r, t)
}
}
dfs(11, 0)
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Build Tree then DFS | O(n) | O(n) | When you want a clear tree structure and standard DFS traversal |
| Hash Map + Implicit DFS | O(n) | O(n) | General case; avoids building the tree and uses constant-time lookups |
Frequently asked questions
Is Path Sum IV easy or hard?
Path Sum IV is generally classified as a Medium problem. The DFS traversal itself is simple, but recognizing how the depth-position encoding determines parent-child relationships is the main challenge.
Path Sum IV Python/Java solution
Implement a hash map where the key represents depth and position and the value is the node value. Run DFS from the root, compute child positions, and accumulate sums until reaching leaves. The same logic works across Python, Java, C++, and Go with O(n) complexity.
How to solve Path Sum IV in O(n)?
Insert each encoded node into a hash map keyed by depth and position. Start DFS from the root and compute child keys using the positional relationship (left: 2p-1, right: 2p). When a node has no children in the map, treat it as a leaf and add the accumulated path sum to the result.
What is the best approach for Path Sum IV?
The hash map with implicit DFS traversal is the most effective approach. Store nodes using a key derived from depth and position, then perform DFS while computing path sums. Child nodes can be located with constant-time hash lookups, producing an O(n) time solution.
Is Path Sum IV asked at Google/Amazon/Meta?
Tree traversal and path sum variations frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact encoding format is less common, the underlying concepts—DFS traversal and tree reconstruction—are common interview topics.
What data structure is used in Path Sum IV?
The solution typically uses a hash table to map encoded node positions to values. Depth-first search is then applied to simulate traversal of the binary tree structure derived from the encoded positions.
What is the time complexity of Path Sum IV?
The optimal solution runs in O(n) time where n is the number of encoded nodes. Each node is inserted into a hash map once and visited once during DFS traversal. Space complexity is also O(n) due to the hash table and recursion stack.