## Problem

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.

Given the below binary tree and sum = 22,

Advertisement

```
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
```

return true, as there exists a root-to-leaf path (5->4->11->2) with a sum of 22.

The binary tree:

```
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL)}
};
```

## Solution

A depth-first search is being used.

```
class Solution {
public:
bool deepFirstSearch(TreeNode *node, int sum, int curSum)
{
if (node == NULL) return false;
if (node->left == NULL && node->right == NULL) {
return curSum + node->val == sum;
}
return deepFirstSearch(node->left, sum, curSum + node->val) || deepFirstSearch(node->right, sum, curSum + node->val);
}
bool hasPathSum(TreeNode *root, int sum) {
return deepFirstSearch(root, sum, 0);
}
};
```

## Leave a Reply