### Problem: Leetcode 112 – Path Sum

**Description:**

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:

```
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 sum 22 is 5 → 4 → 11 → 2.
```

### Example 2:

```
Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There is no root-to-leaf path that sums to 5.
```

### Example 3:

```
Input: root = [], targetSum = 0
Output: false
```

### Analysis:

We need to determine whether there exists a path from the root of the tree to any leaf such that the sum of the node values along that path equals the given `targetSum`

. This can be solved using **depth-first search (DFS)**, where we recursively check each path and subtract the current node’s value from the `targetSum`

as we traverse down the tree.

If at any point we reach a leaf node (a node with no children) and the remaining `targetSum`

equals the value of the leaf node, we return `true`

. If no such path is found, we return `false`

.

### Python Code:

```
def hasPathSum(root, targetSum):
# Base case: If the tree is empty, return False
if not root:
return False
# Check if we are at a leaf node, and if the remaining sum equals the leaf node value
if not root.left and not root.right:
return root.val == targetSum
# Recursively check the left and right subtrees with the updated target sum
return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val)
```

### Example Usage:

```
# Example Tree: [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22
# Output: true (because 5 -> 4 -> 11 -> 2 sums to 22)
```

### Time Complexity:

The time complexity is **O(n)**, where `n`

is the number of nodes in the tree. This is because we visit each node exactly once during the depth-first traversal.

### Space Complexity:

The space complexity is **O(h)**, where `h`

is the height of the tree. In the worst case (for example, in a skewed tree), the recursion stack can go as deep as the height of the tree. In a balanced tree, the height is **O(log n)**, but in the worst case, it can be **O(n)**.