def count_paths(root, S):
if root is None:
return 0
if root.left is None and root.right is None and root.val == S:
return 1
return count_paths(root.left, S) + \
count_paths(root.left, S - root.val) + \
count_paths(root.right, S) + \
count_paths(root.right, S - root.val)
2 Likes
I did something very similar, but I think the time complexity of doubling the number of recursive calls per node is much worse than the solution provided.