✅ EASY || 💯 BEATS-PROOF || 🌟 JAVA || 🧑‍💻 BEGINNER FREINDLY || 🙂 DETAILED EXLANATION
\n\n# \uD83C\uDF1F PROOF\n---\n\n\n\n\n\n# \uD83C\uDF1F Intuition\n---\n Describe your first thoughts on how to solve this problem. \nThe goal is to count all p
```\n```\n# \uD83C\uDF1F PROOF\n---\n![image.png](https://assets.leetcode.com/users/images/0f32385f-cb6f-4d69-92ec-9a10d6f08242_1731833068.5137405.png)\n\n```\n```\n\n# \uD83C\uDF1F Intuition\n---\n<!-- Describe your first thoughts on how to solve this problem. -->\n**The goal is to count all paths in the binary tree whose sum equals `targetSum`. A path can start and end at any node but must traverse downwards. Using prefix sums and a hashmap, we can efficiently track the cumulative sum and identify valid paths.**\n\n```\n```\n# \uD83C\uDF1F Approach\n---\n<!-- Describe your approach to solving the problem. -->\n1. ### **Prefix Sum Concept**:\n\n    - Maintain a cumulative sum (`prefixSum`) for each node as you traverse the tree.\n    - The sum of any path can be represented as the difference between two prefix sums.\n    - For a valid path with sum equal to `targetSum`, the equation is:\n`prefixSum` - `targetSum` exists as a prefix sum in the path to the current node.\n\n2. ### **HashMap for Optimization**:\n\n    - Use a hashmap (`hmap`) to store the count of each prefix sum encountered during traversal.\n    - This enables constant-time lookup to check if a path sum exists.\n\n3. ### **DFS Traversal**:\n\n    - Perform a depth-first traversal to compute prefix sums for all paths.\n    - At each node:\n        - Add its value to the prefix sum.\n        - Check if the difference (`prefixSum` - `targetSum`) exists in the hashmap. If it does, add its count to the result.\n        - Increment the prefix sum\'s count in the hashmap.\n    - After exploring both children, decrement the count of the current prefix sum to backtrack.\n\n4. ### **Edge Case**:\n\n    - Handle the case when the tree is empty by returning 0.\n\n```\n```\n# \uD83C\uDF1F Complexity\n--- \n- ### Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n**$$O(N)$$, where $$N$$ is the number of nodes. Each node is visited once.**\n- ### Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n**$$O(H)$$, where $$H$$ is the height of the tree for the recursion stack, and $$O(N)$$ for the hashmap in the worst case.**\n```\n```\n# \uD83C\uDF1F Code\n---\n```java []\nclass Solution {\n\n    private Map<Long, Integer> hmap;\n    private int count;\n\n    public int pathSum(TreeNode root, int targetSum) {\n        hmap = new HashMap<>();\n        count = 0;\n\n        dfs(root, 0, targetSum);\n\n        return count;\n    }\n\n    private void dfs(TreeNode root, long prefixSum, int targetSum) {\n        if (root == null) return;\n        \n        prefixSum += root.val;\n        \n        if (hmap.containsKey(prefixSum-targetSum)) \n            count += hmap.get(prefixSum-targetSum); \n        \n        if (targetSum == prefixSum) \n            count++;\n\n        hmap.put(prefixSum, hmap.getOrDefault(prefixSum, 0) + 1);\n\n        dfs(root.left, prefixSum, targetSum);\n        dfs(root.right, prefixSum, targetSum);\n\n        hmap.put(prefixSum, hmap.get(prefixSum) - 1);\n    }\n}\n```\n```\n```\n---\n\n![upvote.png](https://assets.leetcode.com/users/images/1609ecdd-f02f-484a-9017-a132c5726f3c_1731833083.813395.png)\n\n---\n```\n```
['Hash Table', 'Depth-First Search', 'Recursion', 'Binary Tree', 'Java']