Course4all
Join us on telegram
Home/dsa/Trees/Path Sum IV

Path Sum IV

Master this topic with zero to advance depth.

Path Sum IV

Tree as array sum.

Hard
Approach 1

Level I: BFS (Iterative path storage)

Intuition

We can build the tree level by level using a queue. For each level, we store the full path sum to each node. When we find a node that has no children in the input set, it's a leaf, and we add its path sum to the total.

Logic

  1. Store all input integers in a Map for quick lookup.
  2. Use a Queue to perform BFS, starting from depth 1, position 1.
  3. Each entry in the Queue is (depth, position, currentSum).
⏱ O(N)💾 O(N)

Detailed Dry Run

Queue starts with [1,1,3]. Next level: [2,1,8], [2,2,4]. Since these have no children, add 8+4=12 to total.

java
public class Main {
    public int pathSum(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) map.put(n / 10, n % 10);
        int total = 0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{1, 1, map.get(11)});
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int d = curr[0], p = curr[1], sum = curr[2];
            int l = (d+1)*10 + (2*p-1), r = (d+1)*10 + (2*p);
            if (!map.containsKey(l) && !map.containsKey(r)) {
                total += sum;
            } else {
                if (map.containsKey(l)) q.add(new int[]{d+1, 2*p-1, sum + map.get(l)});
                if (map.containsKey(r)) q.add(new int[]{d+1, 2*p, sum + map.get(r)});
            }
        }
        return total;
    }
}
Approach 2

Level II: Recursive DFS (State Tracking)

Intuition

We can use a recursive approach that builds the tree logic internally. For any ID ij, its children are (i+1)(2j-1) and (i+1)(2j). We can track the path sum as we recurse down.

Logic

  1. Store all nums in a Map.
  2. Start DFS from 11 with currentSum = 0.
  3. Base case: if key not in Map, return.
⏱ O(N)💾 O(N)

Detailed Dry Run

DFS(11, 0) -> DFS(21, 3) + DFS(22, 3). 21 is leaf -> total += 3+node.val.

java
public class Main {
    int total = 0;
    Map<Integer, Integer> map = new HashMap<>();
    public int pathSum(int[] nums) {
        for (int n : nums) map.put(n / 10, n % 10);
        dfs(11, 0);
        return total;
    }
    private void dfs(int node, int curSum) {
        if (!map.containsKey(node)) return;
        curSum += map.get(node);
        int depth = node / 10, pos = node % 10;
        int l = (depth + 1) * 10 + (2 * pos - 1);
        int r = (depth + 1) * 10 + (2 * pos);
        if (!map.containsKey(l) && !map.containsKey(r)) {
            total += curSum;
        } else {
            dfs(l, curSum); dfs(r, curSum);
        }
    }
}
Approach 3

Level III: Optimal (HashMap with Recursive Sum)

Intuition

In this problem, a tree is given as a list of integers [Depth, Position, Value]. Depth 1 means root, depth 2 is its children. A position P in depth D has children at position 2P-1 and 2P in depth D+1.

Thought Process

  1. Store the tree in a HashMap: key = (depth * 10 + position), value = val.
  2. Perform a DFS starting from the root (ID: 11).
  3. Keep track of the current path sum.
  4. If a node has no children in the Map, it's a leaf. Add the current path sum to the total result.
⏱ O(N) (N is the number of nodes)💾 O(N) (Storage of nodes in Map)

Detailed Dry Run

InputMapDepth/PosPath SumAction
113{11: 3}1, 13Root
215{11: 3, 21: 5}2, 18Left Child
221{11: 3, 21: 5, 22: 1}2, 24Right Child
java
import java.util.*;

public class Main {
    int sum = 0;
    Map<Integer, Integer> map = new HashMap<>();
    public int pathSum(int[] nums) {
        for (int n : nums) map.put(n / 10, n % 10);
        dfs(1, 1, 0);
        return sum;
    }
    private void dfs(int d, int p, int currentSum) {
        int key = d * 10 + p;
        if (!map.containsKey(key)) return;
        currentSum += map.get(key);
        int left = (d + 1) * 10 + (2 * p - 1);
        int right = (d + 1) * 10 + (2 * p);
        if (!map.containsKey(left) && !map.containsKey(right)) {
            sum += currentSum;
            return;
        }
        dfs(d + 1, 2 * p - 1, currentSum);
        dfs(d + 1, 2 * p, currentSum);
    }
}
← Previous QuestionLowest Common Ancestor III
Next Question →Binary Tree Cameras