public int countPaths(TreeNode root, int targetSum)
    {
        int count = 0;
        countPaths(root, targetSum, ref count, new List<int>());
        return count;
    }

    private void countPaths(TreeNode root, int targetSum, ref int count, List<int> sumList)
    {
        // base case
        if (root == null)
        {
            return;
        }
        // add curr node val to each sums and a separate sum
        // => curr val added to prev paths and new path created starting from curr
        for (int i = 0; i < sumList.Count; i++)
        {
            sumList[i] += root.Val;
        }
        sumList.Add(root.Val);
        // check if there's a  valid sum
        foreach (int sum in sumList)
        {
            if (sum == targetSum)
            {
                count++;
            }
        }
        // explore left and right subtrees -> pass new list by value to keep it isolated
        countPaths(root.Left, targetSum, ref count, new List<int>(sumList));
        countPaths(root.Right, targetSum, ref count, new List<int>(sumList));
    }