# Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

```
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
```

return true, as there exist a root-to-leaf path 5 -> 4 -> 11 -> 2 which sum is 22.

## Link here to the repo to solve the problem

👉## 👊 Solution 1

The most intuitive way is to use a recursion here. We want to traverse all the way down until we reach a leaf node, there we want to take the sum of all the paths until this point, if any of them match the targetSum, we return true. Otherwise we want to check every possible branch all the way down to its leaf.

For time complexity, as we visit each node exactly once, thus the time complexity is O(N), where N is the number of nodes.

In terms of space complexity : in the worst case, the tree is completely unbalanced, e.g. each node has only one child node, the recursion call would occur N times (the height of the tree), therefore the storage to keep the call stack would be O(N). But in the best case (the tree is completely balanced), the height of the tree would be log(N). Therefore, the space complexity in this case would be O(log(N)).

```
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public static boolean hasPathSum(TreeNode root, int sum) {
if(root == null) return false;
return helper(root, 0, sum);
}
private static boolean helper(TreeNode node, int currentSum, int targetSum) {
if (node == null) return false;
if (node.left == null && node.right == null) { // when we reach the leaf nodes
return (currentSum + node.val) == targetSum;
} else { // keep going down until we reach the leafs
return helper(node.left, currentSum + node.val, targetSum) || helper(node.right, currentSum + node.val, targetSum);
}
}
}
```

*Question borrowed from “leetcode.com”*