class Solution {
  public int countPaths(TreeNode root, int S) {
    int[] count = new int[1];

    traverse(root, count, S);
    return count[0];
  }

  private void traverse(TreeNode root, int[] count, int S){
    if(root == null) return;

    calc(root,count,S,0);

    traverse(root.left, count, S);
    traverse(root.right,count, S);
  }

  private void calc(TreeNode root, int[] count, int S, int curr){
    if(root == null) return;

    curr += root.val;
    
    if(curr == S) count[0]++;

    calc(root.left,count, S, curr);
    calc(root.right,count, S, curr);
  } 
}