title: number of paths in a binary tree with a given sum
body: <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>