## Path Sum

###### DESCRIPTION (credit Leetcode.com)

Given the root of a binary tree and an integer target, write a recursive function to determine if the tree has a root-to-leaf path where all the values along that path sum to the target.

###### EXAMPLES

**Example 1**:

Input:

`[4, 2, 7, 1, 3, 6, 9] target = 17`

Output: true (the path is 4 -> 7 -> 6)

**Example 2**:

Input:

`[4, 2, 7, 1, 3, 6, 9] target = 13`

Output: false

Run your code to see results here

## Explanation

We can solve this problem using the framework established in the Overview section.

**Return Values**

If I'm at a node in the tree, what values do I need from my child to tell if there's a path from the root to a leaf that sums to the target?

In order for there to be a path from the root to a leaf that sums to the target, there must be a path from either the left or right child to a leaf that sums to target - node.val.

This tells us that each recurisve call should return True if there's a path from the current node to a leaf the sums to the current target, and False otherwise. In the body, we'll make recursive calls to the current node's left and right children, passing in target - node.val for the current target. If either of those calls returns True, then we should return True to the parent.

**Base Case**
If our current node is None, then our subtree is empty and there's no path from the current node to a leaf that sums to the target.

If our current node is a leaf node, then we check if the target is equal to the leaf node's value. If it is, then there's a path from the current node to a leaf that sums to the target.

**Helper Functions**
We need to pass the current target down from parent to children nodes, but this is included in the function signature of the main function, so we don't need to introduce a helper function.

**Global Variables**
The return value of each recurisve call matches the answer to the problem, so we don't need to use any global variables.

## Solution

class Solution:def pathSum(self, root, target):if root is None:return False# if we reach a leaf node, check if the target is equal to the leaf node's valueif not root.left and not root.right:return target == root.valtarget -= root.val# check if there's a path from the current node to a leaf that sums to targetreturn self.pathSum(root.left, target) or self.pathSum(root.right, target)

## Animated Solution

def hasPathSum(root, target):if not root:return Falseif not root.left and not root.right:return target == root.valleft = hasPathSum(root.left, target - root.val)right = hasPathSum(root.right, target - root.val)return left or right

target: 13

## Complexity Analysis

**Time Complexity:** O(N) where N is the number of nodes in the tree. We visit each node exactly once, and each node, we perform a constant amount of work, so the time complexity is O(N).
**Space Complexity:** O(N), we have to allocate space for a total of N (one for each nodes) recursive calls on the call stack.

Loading comments...