The tree problem is very intuitive to be solved via recursion (just like how a tree is defined recursively).

Let `N(r,s)`

be the number of paths with sum as `s`

and `Nr(r,s)`

for those paths **starting from the root**, the recursion idea is straightforward

- N(r, s) = N(rLeft, s) + N(rRight, s) + Nr(rLeft, s-rVal) + Nr(rRight, s-rVal) + (s==rVal? 1:0),

where `Nr(r,s)`

also has recursion

- Nr(r,s) = Nr(rLeft,s-rVal) + Nr(rRight,s-rVal) + (s==rVal? 1:0).

Both base cases are

- N(NULL, s) = 0, Nr(NULL, s) = 0.

```
int pathSum(TreeNode* r, int sum) {
if (!r) return 0; int diff = sum-r->val;
return pathSum(r->left, sum) + pathSumFromRoot(r->left, diff) +
pathSum(r->right, sum) + pathSumFromRoot(r->right, diff) + (diff? 0 : 1);
}
// number of path to sum starting from root
int pathSumFromRoot(TreeNode* r, int sum) {
if (!r) return 0; int diff = sum-r->val;
return pathSumFromRoot(r->left, diff) + pathSumFromRoot(r->right, diff) + (diff? 0 : 1);
}
```