# Easy to understand 26ms C++ solution No map or vector

• Since we need to find out the total number of paths that add up to sum, we just need to pass the original sum or sum - root->val to the next level. If the sum that passed from the parent equals to the current root->val, then add count by one.

The tricky part is, you need to use a boolean has_head variable to keep track whether or not the current node can be a new head or not. For example, the total sum is 8, root value is 3, in this case, you can pass either 8 or 5 to the next level. When you pass 8 to the children, it means that its children can be the new head because root is not in the path in this case. When you pass 5 to the children, then the children cannot be the new head anymore because in this case, root is the head. That's why you need the has_head variable so you know if the current node can be head or not with the given sum value.

``````class Solution {
public:
void countPath(TreeNode* root, int sum, int& count, bool has_head){
if (!root) return;
if (root->val==sum) count++;
countPath(root->left, sum, count, false);
countPath(root->right, sum, count, false);
}
countPath(root->left, sum-root->val, count, true);
countPath(root->right, sum-root->val, count, true);
}
int pathSum(TreeNode* root, int sum) {
int count = 0;
countPath(root, sum, count, false);
return count;
}
};
``````