Close Menu
    What's Hot
    Explore the coolest frontend learning platform !
    Visit NamasteDev
    Thursday, June 4

    Path Sum

    Updated: Algorithms No Comments1 Min Readdevangini123By

    Problem Statement:

    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.

    Examples:

    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 the target sum is shown.

    Example 2:

    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

    Approach 1: (Top-Down)

    • At each node, we add the current node's value to the running sum (currSum).
    • If we reach a leaf node and the sum equals the targetSum, we update ans = true.
    • We recursively check both left and right subtrees.

    Time Complexity:

  • Time Complexity = O(n)

    • Space Complexity:

  • Space Complexity = O(n)

    • Dry Run

    Input: root = [1, 2, 3, null, 4], targetSum = 7

     
Tree Structure: 
        1 
       / \ 
      2   3 
       \
        4
Step-by-step Execution:
traverse(1, 0)
→ newSum = 0 + 1 = 1
→ traverse(2, 1)
→ newSum = 1 + 2 = 3
→ traverse(4, 3)
→ newSum = 3 + 4 = 7
→ Node 4 is a leaf and newSum == targetSum → ans = true
→ traverse(3, 1)
→ newSum = 1 + 3 = 4
→ Node 3 is a leaf and newSum != targetSum → do nothing
Final return value: true

    Output: Result: true

    
var hasPathSum = function(root, targetSum) {
    if(!root) return false;
    let ans = false;
    let traverse = (curr, currSum) => {
        let newSum = currSum + curr.val;
        if(!curr.left && !curr.right) {
            if(newSum === targetSum) {
                ans = ans || true;
            }
        }
        curr.left && traverse(curr.left, newSum);
        curr.right && traverse(curr.right, newSum);
    }
    traverse(root, 0);
    return ans;
}; 
     
    
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def hasPathSum(root, targetSum):
    if not root:
        return False
    ans = [False]  # using list to allow updates inside nested function
    def traverse(curr, currSum):
        newSum = currSum + curr.val
        if not curr.left and not curr.right:
            if newSum == targetSum:
                ans[0] = True
        if curr.left:
            traverse(curr.left, newSum)
        if curr.right:
            traverse(curr.right, newSum)
    traverse(root, 0)
    return ans[0]
            
    
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}
class Solution {
    boolean ans = false;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;

        traverse(root, 0, targetSum);
        return ans;
    }
    private void traverse(TreeNode curr, int currSum, int targetSum) {
        int newSum = currSum + curr.val;
        if (curr.left == null && curr.right == null) {
            if (newSum == targetSum) {
                ans = true;
            }
        }
        if (curr.left != null) traverse(curr.left, newSum, targetSum);
        if (curr.right != null) traverse(curr.right, newSum, targetSum);
    }
}
     
    
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};
bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) return false;
    bool ans = false;
    std::function traverse = [&](TreeNode* curr, int currSum) {
        int newSum = currSum + curr->val;
        if (!curr->left && !curr->right) {
            if (newSum == targetSum) {
                ans = true;
            }
        }
        if (curr->left) traverse(curr->left, newSum);
        if (curr->right) traverse(curr->right, newSum);
    };
    traverse(root, 0);
    return ans;
}
  
    
#include <stdbool.h>
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};
void traverse(struct TreeNode* curr, int currSum, int targetSum, bool* ans) {
    if (!curr) return;
    int newSum = currSum + curr->val;
    if (!curr->left && !curr->right) {
        if (newSum == targetSum) {
            *ans = true;
        }
    }
    if (curr->left) traverse(curr->left, newSum, targetSum, ans);
    if (curr->right) traverse(curr->right, newSum, targetSum, ans);
}
bool hasPathSum(struct TreeNode* root, int targetSum) {
    if (!root) return false;
    bool ans = false;
    traverse(root, 0, targetSum, &ans);
    return ans;
}   
    
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
}
public class Solution {
    public bool HasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        bool ans = false;
        void Traverse(TreeNode curr, int currSum) {
            int newSum = currSum + curr.val;
            if (curr.left == null && curr.right == null) {
                if (newSum == targetSum) {
                    ans = true;
                }
            }
            if (curr.left != null) Traverse(curr.left, newSum);
            if (curr.right != null) Traverse(curr.right, newSum);
        }
        Traverse(root, 0);
        return ans;
    }
}

    Approach 2: Bottom Up

    • Base Case:
      • If the node is null, return false.
      • If it’s a leaf node (no left or right child), check if node.val === targetSum.
    • Recursive Case:
      • Subtract the current node's value from targetSum.
      • Recursively check left and right subtrees with the updated sum.
    • Return:
      • Return true if any path in left or right subtree matches the condition.

    Time Complexity:

  • Time Complexity = O(n)

    • Space Complexity:

  • Space Complexity = O(n)

    • Dry Run

    Input: root = [1, 2, 3, null, 4], targetSum = 7

      1
 / \
2   3
 \
  4

Recursive Calls:
→ hasPathSum(1, 7)
   → node is not null and not a leaf
   → leftSubTreeHasPathSum = hasPathSum(2, 6)
       → node is not null and not a leaf
       → leftSubTreeHasPathSum = hasPathSum(null, 4) = false
       → rightSubTreeHasPathSum = hasPathSum(4, 4)
           → node is a leaf
           → root.val === targetSum → 4 === 4 → true
       → return true
   → rightSubTreeHasPathSum = hasPathSum(3, 6)
       → node is a leaf
       → root.val === targetSum → 3 === 6 → false
   → return true || false → true

    Output: Result: true

    
var hasPathSum = function(root, targetSum) {
    if(!root) return false;
    if(!root.left && !root.right) {
        return root.val === targetSum;
    } 
    let leftSubTreeHasPathSum = hasPathSum(root.left, targetSum - root.val);
    let rightSubTreeHasPathSum = hasPathSum(root.right, targetSum - root.val);

    return leftSubTreeHasPathSum || rightSubTreeHasPathSum;
};
            
    
cdef hasPathSum(root, targetSum):
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == targetSum
    left = hasPathSum(root.left, targetSum - root.val)
    right = hasPathSum(root.right, targetSum - root.val)
    return left or right
            
    
public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }
    boolean left = hasPathSum(root.left, targetSum - root.val);
    boolean right = hasPathSum(root.right, targetSum - root.val);
    return left || right;
}   
    
bool hasPathSum(TreeNode* root, int targetSum) {
    if (root == nullptr) return false;
    if (root->left == nullptr && root->right == nullptr) {
        return root->val == targetSum;
    }
    bool left = hasPathSum(root->left, targetSum - root->val);
    bool right = hasPathSum(root->right, targetSum - root->val);
    return left || right;
}
 
    
bool hasPathSum(struct TreeNode* root, int targetSum) {
    if (root == NULL) return false;
    if (root->left == NULL && root->right == NULL) {
        return root->val == targetSum;
    }
    bool left = hasPathSum(root->left, targetSum - root->val);
    bool right = hasPathSum(root->right, targetSum - root->val);
    return left || right;
}

    
public bool HasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }
    bool left = HasPathSum(root.left, targetSum - root.val);
    bool right = HasPathSum(root.right, targetSum - root.val);
    return left || right;
}

    Keep Reading

    Add A Comment
    Leave A Reply

    Demo

    Courses

    Community

    Contact Us