number of paths in a binary tree with a given sum
<p>I am solving the problem <a href="https://leetcode.com/problems/path-sum-iii/" rel="nofollow noreferrer">https://leetcode.com/problems/path-sum-iii/</a>
I'll also briefly mention it here:
Find the number of paths in a Binary tree whose sum = sum. The path does not necessarily have to begin (end) at the root (leaf). As long as the path goes downward it should be considered as a valid path.</p>

<p>Here is my solution:</p>

<pre><code>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class Solution {
    public int pathSum(TreeNode root, int sum) {
        int path = 0;
        if(root.val == sum)
            return 1;
        else if(root.left == null &amp;&amp; root.right == null)
            return 0;
        if(root.left != null){
            path += pathSum(root.left, sum - root.val);
            path += pathSum(root.left, sum);
        }
        if(root.right != null){
            path += pathSum(root.right, sum - root.val);
            path += pathSum(root.right, sum);
        }
        return path;
    }
}
</code></pre>

<p>The answer as per their system is 3, but I am getting the answer as 4 for the following input:</p>

<pre><code>root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -&gt; 3
2.  5 -&gt; 2 -&gt; 1
3. -3 -&gt; 11
</code></pre>

<p>I have spent hours trying to reason why my code wold not work, but I cannot figure out the problem.</p>

<p>Sorry for a naive question :( But this is killing me!</p>