Path Sum III - Practice Coding Problems

Path Sum III - Problem

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

A path can start from any node and end at any descendant of that node, as long as the direction is always downward.

Input & Output

Example 1 — Basic Tree

$ Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8

› Output: 3

💡 Note: Three paths sum to 8: (5→3), (5→2→1), and (-3→11)

Example 2 — Simple Tree

$ Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

› Output: 3

💡 Note: Paths: (5→4→11→2), (5→8→4→5), and (4→11→7)

Example 3 — Single Node

$ Input: root = [1], targetSum = 1

› Output: 1

💡 Note: Only one node with value 1, which equals targetSum

Constraints

The number of nodes in the tree is in the range [0, 1000]
-10⁹ ≤ Node.val ≤ 10⁹
-1000 ≤ targetSum ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with integer values and target sum

Find Paths

Identify all downward paths summing to target

Count Result

Return total number of valid paths

Key Takeaway

🎯 Key Insight: Use prefix sums to avoid recalculating overlapping path segments

Asked in

a Amazon 45 G Google 35 f Facebook 28 M Microsoft 22

The key insight is using prefix sums with a hash map to avoid redundant path calculations. Instead of checking every possible path separately, we track running sums during DFS and use the map to instantly find how many previous paths can combine with the current node to form valid paths. Best approach uses prefix sum technique with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum with Hash Map	O(n)	O(n)	Use prefix sums and hash map to find paths efficiently in one traversal
Brute Force - Start from Every Node	O(n²)	O(h)	For each node, check all downward paths starting from that node

Prefix Sum with Hash Map — Algorithm Steps

Traverse tree with DFS maintaining prefix sum
Store prefix sum frequencies in hash map
For each node, check if (currentSum - targetSum) exists in map
Update map with current prefix sum, recurse, then backtrack

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Prefix

Maintain running sum and frequency map

Check Difference

Look for (currentSum - target) in map

Backtrack

Remove current sum when returning from recursion

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct PrefixEntry {
    long long sum;
    int count;
    struct PrefixEntry* next;
};

struct HashMap {
    struct PrefixEntry* buckets[1000];
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int hash(long long sum) {
    return abs((int)(sum % 1000));
}

int getCount(struct HashMap* map, long long sum) {
    int idx = hash(sum);
    struct PrefixEntry* entry = map->buckets[idx];
    while (entry) {
        if (entry->sum == sum) return entry->count;
        entry = entry->next;
    }
    return 0;
}

void putCount(struct HashMap* map, long long sum, int count) {
    int idx = hash(sum);
    struct PrefixEntry* entry = map->buckets[idx];
    while (entry) {
        if (entry->sum == sum) {
            entry->count = count;
            return;
        }
        entry = entry->next;
    }
    
    entry = (struct PrefixEntry*)malloc(sizeof(struct PrefixEntry));
    entry->sum = sum;
    entry->count = count;
    entry->next = map->buckets[idx];
    map->buckets[idx] = entry;
}

int dfs(struct TreeNode* node, long long currentSum, int targetSum, struct HashMap* prefixSumCount) {
    if (!node) return 0;
    
    currentSum += node->val;
    
    int pathCount = getCount(prefixSumCount, currentSum - targetSum);
    
    int currentCount = getCount(prefixSumCount, currentSum);
    putCount(prefixSumCount, currentSum, currentCount + 1);
    
    pathCount += dfs(node->left, currentSum, targetSum, prefixSumCount);
    pathCount += dfs(node->right, currentSum, targetSum, prefixSumCount);
    
    currentCount = getCount(prefixSumCount, currentSum);
    putCount(prefixSumCount, currentSum, currentCount - 1);
    
    return pathCount;
}

int solution(struct TreeNode* root, int targetSum) {
    struct HashMap prefixSumCount = {0};
    putCount(&prefixSumCount, 0, 1);
    return dfs(root, 0, targetSum, &prefixSumCount);
}

struct TreeNode* buildTree(int* arr, int size) {
    if (size == 0) return NULL;
    
    struct TreeNode* root = createNode(arr[0]);
    struct TreeNode** queue = (struct TreeNode**)malloc(size * sizeof(struct TreeNode*));
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    for (int i = 1; i < size; i += 2) {
        struct TreeNode* node = queue[front++];
        
        if (arr[i] != -1001) {
            node->left = createNode(arr[i]);
            queue[rear++] = node->left;
        }
        
        if (i + 1 < size && arr[i + 1] != -1001) {
            node->right = createNode(arr[i + 1]);
            queue[rear++] = node->right;
        }
    }
    
    free(queue);
    return root;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000];
    int size = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        if (strcmp(token, "null") == 0) {
            arr[size++] = -1001;
        } else {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n ");
    }
    
    int targetSum;
    scanf("%d", &targetSum);
    
    struct TreeNode* root = buildTree(arr, size);
    int result = solution(root, targetSum);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once in DFS traversal

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n prefix sums plus recursion stack

⚡ Linearithmic Space

316.1K Views

High Frequency

~25 min Avg. Time

8.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum with Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler