# 112. Path Sum

### Description

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.

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

### Constraints

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/root-to-leaf-path-sum-equal-to-a-given-number/)
* [Leetcode](https://leetcode.com/problems/path-sum/)
* [ProgramCreek](https://www.programcreek.com/2013/01/leetcode-path-sum/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:**

tree=\[5,4,8,11,null,13,4,7,2,null,null,null,1]

sum=22

**Output:** true

**Explanation:**

<div align="left"><img src="https://1091135627-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmU-aGQcUvtjjAH8_3%2F-MFzTNxztUJEPqYB9FiI%2F-MFzUEGTxISnoqihIfUx%2Fimage.png?alt=media&#x26;token=c80ecc21-d427-4dc1-a374-1bb55d03f0fe" alt=""></div>
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="TreeNode" %}

```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;
    }
}
```

{% endtab %}

{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        
        sum -= root.val;
        if(root.left == null && root.right == null) {
            return sum == 0;
        }
        
        return hasPathSum(root.left, sum) || 
                hasPathSum(root.right, sum);
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

* Print Palindromic Paths of Binary tree - [GFG](https://www.geeksforgeeks.org/print-palindromic-paths-of-binary-tree/)