Skip to main content

Path Sum

Problem 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.

Examples​

Example 1:

LeetCode Problem - Binary Tree

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Example 2:

LeetCode Problem - Binary Tree

Input: root = [1,2,3] targetSum = 5
Output: false

Constraints​

  • The number of nodes in the tree is in the range [0,5000][0, 5000].

  • −1000≤Node.val≤1000-1000 \leq \text{Node.val} \leq 1000


Solution for Binary Tree Problem​

Intuition And Approach​

To solve this problem, we can use a depth-first search (DFS) to traverse the tree from the root to the leaves, while keeping track of the sum of the values along the current path.

  1. DFS Traversal: Traverse the tree from the root to the leaves.
  2. Sum Tracking: Keep track of the sum of the values along the current path.
  3. Leaf Check: When a leaf node is reached, check if the path sum equals targetSum.

Code in Different Languages​

Written by @Vipullakum007
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if (root.left == null && root.right == null) return targetSum == root.val;
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}
}

Complexity Analysis​

  • Time Complexity: O(n)O(n) where n is the number of nodes in the binary tree.
  • Space Complexity: O(h)O(h) where h is the height of the tree.