# 4-line implementation C++ DFS solution with sum from root as helper (with explanation)

• 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);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.