🔥BEATS 💯 % 🎯 | 2 APPROACH |EASY & TRICKY👏| JAVA | C | C++ | PYTHON| JAVASCRIPT | DART 
IntuitionThe problem requires counting the number of paths in a binary tree whose sum equals a given target. The brute force approach of checking all possible p
![image.png](https://assets.leetcode.com/users/images/b598ad6d-bbdc-4e3f-8095-81d1b1f7aacf_1739201114.413435.png)

---
![1000086413.png](https://assets.leetcode.com/users/images/b81143dd-29ec-4765-90d1-670ceee28f1a_1739201455.5150986.png)

----

# **Intuition**
The problem requires counting the number of paths in a binary tree whose sum equals a given target. The **brute force approach** of checking all possible paths from each node would be **O(n²)** in complexity. Instead, we can **optimize** this using **prefix sum** and a **hash map**.

### **Key Idea:**
- At each node, we maintain a **running prefix sum** (sum of all node values from the root to the current node).
- If a previous prefix sum `prefixSum[x]` exists such that  
  \[
  \text{currentSum} - \text{targetSum} = x
  \]
  then there exists a **valid path** from that node to the current node.

- We use a **hash map (dictionary)** to store these prefix sums efficiently.

---

# **Approach (1) TRCIKY**
1. **Use a Hash Map (`prefixSumCount`)**:
   - Store **prefix sums** and their counts to track the number of times each sum has appeared.

2. **Depth-First Search (DFS) Traversal**:
   - Start at the root and maintain a `currentSum` (prefix sum).
   - Check how many times `currentSum - targetSum` has occurred → This gives the count of valid paths ending at the current node.
   - Add `currentSum` to the hash map.
   - Recur for **left and right subtrees**.
   - **Backtrack**: Remove `currentSum` when returning to the previous node to maintain correctness.

---

# **Complexity Analysis**
- **Time Complexity**:  
  - **O(n)** → Each node is visited once.
- **Space Complexity**:  
  - **O(n)** in the worst case (skewed tree) due to recursion stack and hash map storage.

---


```dart []
import 'dart:collection';

// class TreeNode {
//   int val;
//   TreeNode? left;
//   TreeNode? right;
//   TreeNode(this.val, [this.left, this.right]);
// }

class Solution {
  int pathSum(TreeNode? root, int targetSum) {
    Map<int, int> prefixSumCount = {0: 1}; // To handle cases where entire path matches targetSum
    return dfs(root, 0, targetSum, prefixSumCount);
  }

  int dfs(TreeNode? node, int currentSum, int targetSum, Map<int, int> prefixSumCount) {
    if (node == null) return 0;
    
    // Current prefix sum
    currentSum += node.val;
    
    // Count paths ending at this node with sum = targetSum
    int count = prefixSumCount[currentSum - targetSum] ?? 0;
    
    // Update prefix sum map
    prefixSumCount[currentSum] = (prefixSumCount[currentSum] ?? 0) + 1;
    
    // Recur for left and right children
    count += dfs(node.left, currentSum, targetSum, prefixSumCount);
    count += dfs(node.right, currentSum, targetSum, prefixSumCount);
    
    // Backtrack: Remove currentSum from map to maintain only current path sums
    prefixSumCount[currentSum] = prefixSumCount[currentSum]! - 1;
    if (prefixSumCount[currentSum] == 0) {
      prefixSumCount.remove(currentSum);
    }
    
    return count;
  }
}
```


```java []
import java.util.HashMap;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        HashMap<Integer, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0, 1); // To handle cases where entire path matches targetSum
        return dfs(root, 0, targetSum, prefixSumCount);
    }

    private int dfs(TreeNode node, int currentSum, int targetSum, HashMap<Integer, Integer> prefixSumCount) {
        if (node == null) return 0;
        
        currentSum += node.val;
        int count = prefixSumCount.getOrDefault(currentSum - targetSum, 0);
        
        prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
        
        count += dfs(node.left, currentSum, targetSum, prefixSumCount);
        count += dfs(node.right, currentSum, targetSum, prefixSumCount);
        
        prefixSumCount.put(currentSum, prefixSumCount.get(currentSum) - 1);
        if (prefixSumCount.get(currentSum) == 0) {
            prefixSumCount.remove(currentSum);
        }
        
        return count;
    }
}
```


```python []
from collections import defaultdict

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        prefixSumCount = defaultdict(int)
        prefixSumCount[0] = 1  # To handle cases where the entire path matches targetSum
        return self.dfs(root, 0, targetSum, prefixSumCount)

    def dfs(self, node, currentSum, targetSum, prefixSumCount):
        if not node:
            return 0

        currentSum += node.val
        count = prefixSumCount[currentSum - targetSum]
        
        prefixSumCount[currentSum] += 1
        
        count += self.dfs(node.left, currentSum, targetSum, prefixSumCount)
        count += self.dfs(node.right, currentSum, targetSum, prefixSumCount)
        
        prefixSumCount[currentSum] -= 1
        if prefixSumCount[currentSum] == 0:
            del prefixSumCount[currentSum]
        
        return count
```


```cpp []
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<int, int> prefixSumCount;
        prefixSumCount[0] = 1; // To handle cases where entire path matches targetSum
        return dfs(root, 0, targetSum, prefixSumCount);
    }

private:
    int dfs(TreeNode* node, int currentSum, int targetSum, unordered_map<int, int>& prefixSumCount) {
        if (!node) return 0;

        currentSum += node->val;
        int count = prefixSumCount[currentSum - targetSum];

        prefixSumCount[currentSum]++;
        count += dfs(node->left, currentSum, targetSum, prefixSumCount);
        count += dfs(node->right, currentSum, targetSum, prefixSumCount);

        prefixSumCount[currentSum]--;
        if (prefixSumCount[currentSum] == 0) {
            prefixSumCount.erase(currentSum);
        }

        return count;
    }
};
```


```javascript []
var pathSum = function(root, targetSum) {
    let prefixSumCount = new Map();
    prefixSumCount.set(0, 1); // To handle cases where entire path matches targetSum
    
    const dfs = (node, currentSum) => {
        if (!node) return 0;
        
        currentSum += node.val;
        let count = prefixSumCount.get(currentSum - targetSum) || 0;
        
        prefixSumCount.set(currentSum, (prefixSumCount.get(currentSum) || 0) + 1);
        
        count += dfs(node.left, currentSum);
        count += dfs(node.right, currentSum);
        
        prefixSumCount.set(currentSum, prefixSumCount.get(currentSum) - 1);
        if (prefixSumCount.get(currentSum) === 0) {
            prefixSumCount.delete(currentSum);
        }
        
        return count;
    };
    
    return dfs(root, 0);
};
```

---
---

![1000088581.png](https://assets.leetcode.com/users/images/cfc2ccd7-ad6e-422f-82bd-4b9fcb1670a0_1739460717.3881035.png)


# **Intuition**  
The problem requires us to find the number of **paths** in a binary tree where the sum of node values **equals** a given target sum.  

A **path** can start **from any node** and must move **downward** (parent to child).  

To solve this, we need an efficient way to **check all possible paths** ending at each node while avoiding redundant calculations.

---

# **Approach (2) EASY**  
1. **Use a recursive depth-first search (DFS)**  
   - Traverse the tree using DFS.
   - Maintain a **list of node values** from the root to the current node.  

2. **Check all subarrays (prefix sums) that end at the current node**  
   - Iterate **backward** through the list and compute the sum.  
   - If the sum matches the `targetSum`, increment the count.  

3. **Backtracking**  
   - Since we modify the list during recursion, remove the last node after exploring both left and right subtrees.  

---

# **Complexity Analysis**  
- **Time Complexity:**  
  - Each node is visited **once** → **O(n)**.  
  - For each node, we check all ancestor sums → **O(n)** (in worst case, when the tree is a linked list).  
  - **Total: O(n²) in the worst case**, but **O(n log n) on average for balanced trees**.  

- **Space Complexity:**  
  - **O(n)** for recursion depth in a skewed tree.  
  - **O(log n)** for a balanced tree.  

---


```dart []
import 'dart:collection';

// class TreeNode {
//   int val;
//   TreeNode? left;
//   TreeNode? right;
//   TreeNode(this.val, [this.left, this.right]);
// }

class Solution {
  int count = 0;

  int pathSum(TreeNode? root, int targetSum) {
    helperPathSum(root, targetSum, []);
    return count;
  }

  void helperPathSum(TreeNode? root, int targetSum, List<int> path) {
    if (root == null) return;

    path.add(root.val);
    int sum = 0;

    // Check for valid subarrays (prefix sums)
    for (int i = path.length - 1; i >= 0; i--) {
      sum += path[i];
      if (sum == targetSum) count++;
    }

    // Recursive DFS on left and right subtrees
    helperPathSum(root.left, targetSum, path);
    helperPathSum(root.right, targetSum, path);

    // Backtrack
    path.removeLast();
  }
}
```


```java []
import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    int count = 0;

    public int pathSum(TreeNode root, int targetSum) {
        helperPathSum(root, targetSum, new ArrayList<>());
        return count;
    }

    private void helperPathSum(TreeNode root, int targetSum, List<Integer> path) {
        if (root == null) return;

        path.add(root.val);
        int sum = 0;

        // Check all subarrays ending at this node
        for (int i = path.size() - 1; i >= 0; i--) {
            sum += path.get(i);
            if (sum == targetSum) count++;
        }

        helperPathSum(root.left, targetSum, path);
        helperPathSum(root.right, targetSum, path);

        // Backtrack
        path.remove(path.size() - 1);
    }
}
```


```python []
from typing import Optional, List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def __init__(self):
        self.count = 0

    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def helper(root, path):
            if not root:
                return
            
            path.append(root.val)
            sum_ = 0
            
            # Check all prefix sums
            for i in range(len(path) - 1, -1, -1):
                sum_ += path[i]
                if sum_ == targetSum:
                    self.count += 1
            
            helper(root.left, path)
            helper(root.right, path)
            
            # Backtrack
            path.pop()

        helper(root, [])
        return self.count
```


```cpp []
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int count = 0;

    int pathSum(TreeNode* root, int targetSum) {
        vector<int> path;
        helperPathSum(root, targetSum, path);
        return count;
    }

    void helperPathSum(TreeNode* root, int targetSum, vector<int>& path) {
        if (!root) return;

        path.push_back(root->val);
        int sum = 0;

        // Check all prefix sums
        for (int i = path.size() - 1; i >= 0; i--) {
            sum += path[i];
            if (sum == targetSum) count++;
        }

        helperPathSum(root->left, targetSum, path);
        helperPathSum(root->right, targetSum, path);

        // Backtrack
        path.pop_back();
    }
};
```


```javascript []
class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

var pathSum = function(root, targetSum) {
    let count = 0;

    function helper(root, path) {
        if (!root) return;

        path.push(root.val);
        let sum = 0;

        // Check prefix sums
        for (let i = path.length - 1; i >= 0; i--) {
            sum += path[i];
            if (sum === targetSum) count++;
        }

        helper(root.left, path);
        helper(root.right, path);

        // Backtrack
        path.pop();
    }

    helper(root, []);
    return count;
};
```

---

# **Summary**
| Language  | Time Complexity | Space Complexity |
|-----------|----------------|----------------|
| **Dart**  | **O(n²) worst case, O(n log n) average** | **O(n)** |
| **Java**  | **O(n²) worst case, O(n log n) average** | **O(n)** |
| **Python** | **O(n²) worst case, O(n log n) average** | **O(n)** |
| **C++**   | **O(n²) worst case, O(n log n) average** | **O(n)** |
| **JavaScript** | **O(n²) worst case, O(n log n) average** | **O(n)** |

The approach efficiently finds all paths that sum to `targetSum` using **prefix sum checking** and **backtracking**. 🚀


----


![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}
['Tree', 'Depth-First Search', 'C', 'Binary Tree', 'Prefix Sum', 'C++', 'Java', 'Python3', 'JavaScript', 'Dart']