C++ Easy to Understand Bruteforce + Optimised Solution || Explained with recusrsive tree diagram :)
Approach is simple just we have to find all the possible path and check wheather it is equal to sum or not.\nTake a vector to store the path while traversing th
**Approach is simple just we have to find all the possible path and check wheather it is equal to sum or not.**\n**Take a vector to store the path while traversing the tree.**\n### ***Recursive tree diagram :***\n\n![image](https://assets.leetcode.com/users/images/428e139f-9fab-4dc3-995d-0a4734f1902e_1651326452.8400233.jpeg)\n\n**NOTE :** *While adding values from vector, always start adding from the recently added node(i.e.from the end of vector).*\n\n**Below is the implementation of above approach :**\n\n```\npublic:\n    int count = 0;\n    void helper(TreeNode* root, int targetSum,vector<int> &path)\n    {\n        if(!root){\n            return;\n        }\n        \n        // push current node inside the path vector\n        path.push_back(root->val);  \n        helper(root->left,targetSum,path);\n        helper(root->right,targetSum,path);\n        \n        int size = path.size();\n        long long int sum = 0;\n        for(int i = size - 1 ; i >= 0; --i){\n            sum += path[i];\n            if(sum == targetSum){\n                count++;\n            } \n        }\n        \n        // remove the current node, in otherwords backtrack\n        path.pop_back();\n    }\n    \n    int pathSum(TreeNode* root, int targetSum)\n    {\n        vector<int> path; // to store the path \n        helper(root,targetSum,path);\n        return count;\n    }\n};\n```\n***T.C : BestCase O(n*h) and Worst case O(n^2)**\n\n### **Optimised solution using maps by storing prefix sum :**\nI will advice you to solve this problem *https://leetcode.com/problems/subarray-sum-equals-k/ *first before moving to this solution :)\n```\nclass Solution {\npublic:\n int pathSum(TreeNode* root, int tsum) {\n        unordered_map<int, int> m;\n        m[0]++;  // m[0] = 1  : if currsum - k = 0, then it means that currsum = k for that we have to be already map 0 with freq 1 i.e.[0] -> 1\n        \n        int count = 0;\n        helper(root, 0, tsum, count, m);\n        return count;\n    }\n    \n    void helper(TreeNode *p, long int cur, int tsum, int &count, unordered_map<int, int> &m) {\n        if (!p) return;\n        \n        cur += p->val;\n        if (m.find(cur - tsum) != m.end()){\n            count += m[cur - tsum];\n        }\n        m[cur]++;  // increment freq of current sum in map\n        \n        helper(p->left, cur, tsum, count, m);\n        helper(p->right, cur, tsum, count, m);\n        \n        m[cur]--;  // decrement freq of current sum from map\n   }\n};\n```\n**TC : O(n)**\n\n\n\n*If you liked it please upvote my solution :)*
['Depth-First Search', 'Recursion', 'C', 'Binary Tree']