# Path Sum
**Difficulty:** EASY
[External](https://leetcode.com/problems/path-sum)
Canonical: https://scaleengineer.com/dsa/problems/path-sum
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal), [TikTok](https://scaleengineer.com/companies/tiktok), [Datadog](https://scaleengineer.com/companies/datadog)
---
## 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:**

![](https://assets.glich.co/dsa/path-sum/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/path-sum/image1.jpg) 

**Input:** root = [1,2,3], targetSum = 5
**Output:** false
**Explanation:** There are 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.

**Example 3:**

**Input:** root = [], targetSum = 0
**Output:** false
**Explanation:** Since the tree is empty, there are no root-to-leaf paths.

**Constraints:**

* The number of nodes in the tree is in the range `[0, 5000]`.
* `-1000 <= Node.val <= 1000`
* `-1000 <= targetSum <= 1000`

# Approaches
## Recursive Depth-First Search
This approach uses recursion to traverse the tree in a depth-first manner. The core idea is to subtract the current node's value from the `targetSum` and pass this new sum to its children. The recursion continues until a leaf node is reached, at which point we check if the accumulated path sum equals the target.
**Time:** O(N) · **Space:** O(H)
**Pros:** Very intuitive and easy to read.; The code is concise and directly reflects the problem's recursive structure.
**Cons:** For very deep trees, this can lead to a `StackOverflowError` due to the depth of the recursion stack.
### Explanation
The algorithm defines a function that takes a tree node and the remaining sum required to reach the target.

- **Base Case 1:** If the current node is `null`, it means we've traversed past a leaf without finding a valid path from that branch, so we return `false`.
- **Path Sum Update:** We update the required sum by subtracting the current node's value: `newTargetSum = currentSum - node.val`.
- **Base Case 2 (Leaf Node):** If the current node is a leaf (it has no left or right child), we check if its value equals the remaining `targetSum`. If it does, it means the path from the root to this leaf adds up to the original `targetSum`, so we return `true`.
- **Recursive Step:** If the current node is not a leaf, we recursively call the function for its left and right children with the updated `targetSum`. If either of these calls returns `true` (meaning a valid path was found in either the left or right subtree), we return `true`. Otherwise, we return `false`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        
        // If it's a leaf node, check if its value equals the remaining targetSum
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }
        
        // Recursively call for left and right children with updated targetSum
        boolean hasPathInLeft = hasPathSum(root.left, targetSum - root.val);
        boolean hasPathInRight = hasPathSum(root.right, targetSum - root.val);
        
        return hasPathInLeft || hasPathInRight;
    }
}
```
### Algorithm
- 1. Check if the `root` is `null`. If so, return `false` as there are no paths.
- 2. Check if the current `root` is a leaf node (`root.left == null && root.right == null`).
- 3. If it is a leaf, return `true` if `root.val == targetSum`, otherwise `false`.
- 4. If it's not a leaf, recursively call `hasPathSum` for the left child with `targetSum - root.val`.
- 5. Recursively call `hasPathSum` for the right child with `targetSum - root.val`.
- 6. Return `true` if either of the recursive calls returns `true`, indicating a path was found.

## Iterative Traversal (DFS or BFS)
An alternative to recursion is to use an iterative approach with an explicit data structure, like a `Stack` for Depth-First Search (DFS) or a `Queue` for Breadth-First Search (BFS). This approach avoids the limitations of the recursion stack depth and can be more efficient in terms of space for certain tree structures.
**Time:** O(N) · **Space:** O(H) for DFS, O(W) for BFS
**Pros:** Avoids `StackOverflowError` for very deep trees, making it more robust than the recursive solution.; The space complexity can be better than the alternative depending on the tree's shape (DFS is better for wide trees, BFS for deep/skewed trees).
**Cons:** The code is generally more verbose and less intuitive than the recursive counterpart.; Requires managing an explicit data structure (stack or queue).
### Explanation
We can simulate the recursive DFS approach using an explicit `Stack`. The idea is to maintain a stack of nodes to visit and another stack to store the remaining sum corresponding to each node.

- **Initialization:** If the root is `null`, return `false`. Otherwise, push the `root` node onto a `nodeStack` and the initial remaining sum (`targetSum - root.val`) onto a `sumStack`.
- **Traversal Loop:** While the stacks are not empty, pop a node and its corresponding sum.
- **Leaf Check:** If the popped node is a leaf node and its corresponding remaining sum is zero, we have found a valid path. Return `true`.
- **Push Children:** If the node is not a leaf, push its children (if they exist) onto the `nodeStack`. For each child, push the updated remaining sum (`currentSum - child.val`) onto the `sumStack`.
- **No Path Found:** If the loop completes without returning, it means no such path exists. Return `false`.

A similar logic can be applied using a `Queue` for a BFS traversal, where nodes and sums are enqueued and dequeued instead of pushed and popped.

```java
// Iterative DFS using a Stack
import java.util.Stack;

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Integer> sumStack = new Stack<>();
        
        nodeStack.push(root);
        sumStack.push(targetSum - root.val);

        while (!nodeStack.isEmpty()) {
            TreeNode currentNode = nodeStack.pop();
            int currentSum = sumStack.pop();

            if (currentNode.left == null && currentNode.right == null && currentSum == 0) {
                return true;
            }

            if (currentNode.right != null) {
                nodeStack.push(currentNode.right);
                sumStack.push(currentSum - currentNode.right.val);
            }
            if (currentNode.left != null) {
                nodeStack.push(currentNode.left);
                sumStack.push(currentSum - currentNode.left.val);
            }
        }
        return false;
    }
}
```
### Algorithm
- 1. If `root` is `null`, return `false`.
- 2. Create a `nodeStack` and a `sumStack`.
- 3. Push `root` to `nodeStack` and `targetSum - root.val` to `sumStack`.
- 4. Loop as long as `nodeStack` is not empty:
    - a. Pop `currentNode` from `nodeStack` and `currentSum` from `sumStack`.
    - b. If `currentNode` is a leaf and `currentSum` is 0, return `true`.
    - c. If `currentNode.right` exists, push it to `nodeStack` and push `currentSum - currentNode.right.val` to `sumStack`.
    - d. If `currentNode.left` exists, push it to `nodeStack` and push `currentSum - currentNode.left.val` to `sumStack`.
- 5. If the loop finishes, return `false`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean hasPathSum ( TreeNode root , int targetSum ) { return dfs ( root , targetSum ); } private boolean dfs ( TreeNode root , int s ) { if ( root == null ) { return false ; } s -= root . val ; if ( root . left == null && root . right == null && s == 0 ) { return true ; } return dfs ( root . left , s ) || dfs ( root . right , s ); } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} targetSum * @return {boolean} */ var hasPathSum =
  function (root, targetSum) {
    function dfs(root, s) {
      if (!root) return false;
      s += root.val;
      if (!root.left && !root.right && s == targetSum) return true;
      return dfs(root.left, s) || dfs(root.right, s);
    }
    return dfs(root, 0);
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool hasPathSum ( TreeNode * root , int targetSum ) { function < bool ( TreeNode * , int ) > dfs = [ & ]( TreeNode * root , int s ) -> int { if ( ! root ) return false ; s += root -> val ; if ( ! root -> left && ! root -> right && s == targetSum ) return true ; return dfs ( root -> left , s ) || dfs ( root -> right , s ); }; return dfs ( root , 0 ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def hasPathSum ( self , root : Optional [ TreeNode ], targetSum : int ) -> bool : def dfs ( root , s ): if root is None : return False s += root . val if root . left is None and root . right is None and s == targetSum : return True return dfs ( root . left , s ) or dfs ( root . right , s ) return dfs ( root , 0 )
```