# Tree - Path Sum

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

DFS

## Problem

Given the `root`

of a binary tree and an integer `targetSum`

, return `true`

if the tree has a **root-to-leaf** path such that adding up all the values along the path equals `targetSum`

. A **leaf** is a node with no children.

**Example 1:**

1
2
3

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

**Example 2:**

1
2
3
4
5
6

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

## Solution

Since the sum is different for each path we need to track it for every traversal. A simple way to implement this is add it as a function argument. The function call stack will preserve all the intermediate values as calculated at each node level.

Our `dfs()`

function will look like this:

1
2

def dfs(root, path_sum):
...

As always, we shall start with the base case. Whenever we reach a leaf node we can compare if the `path_sum==target_sum`

and return the boolean result.

1
2

if not root.left and not root.right:
return path_sum==target_sum

However, before we compare `path_sum==target_sum`

, we need to update `path_sum`

.

1

path_sum +=root.val

The next step is to traverse through the tree.

1
2
3
4
5
6

if root.left and root.right:
return dfs(root.left,path_sum) or dfs(root.right,path_sum)
elif root.left:
return dfs(root.left,path_sum)
else:
return dfs(root.right,path_sum)

In case of a edge case where `root=[]`

, you can validate that before calling the `dfs()`

function.

1
2

if not root:
return False

Finally return the `dfs(root,0)`

.

1

return dfs(root,0)

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def has_path_sum(root, target_sum):
if not root:
return False
def dfs(root,path_sum):
path_sum+= root.val
if not root.left and not root.right:
return path_sum == target_sum
if root.left and root.right:
return dfs(root.left,path_sum) or dfs(root.right,path_sum)
elif root.left:
return dfs(root.left,path_sum)
else:
return dfs(root.right,path_sum)
return dfs(root,0)

Now, there is a bit shorter version. Here is the code below. If you have understood the above code, the below one should be very similar to understand.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def has_path_sum(root, target_sum):
def dfs(root,path_sum):
if not root:
return False
path_sum+= root.val
if not root.left and not root.right:
return path_sum == target_sum
return dfs(root.left,path_sum) or dfs(root.right,path_sum)
return dfs(root,0)