Check for Root-to-Leaf Path with Target Sum

Problem Statement:

Given a binary tree and an integer target, check whether there is a root-to-leaf path with its sum equal to the target.

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

Constraints:

• 1 ≤ number of nodes ≤ 10^4
• 1 ≤ target ≤ 10^6

Solution Approach:

Observation: To determine if there is a root-to-leaf path with a given sum, we need to explore all paths from the root to the leaf nodes and check their sums against the target. We can achieve this using a recursive depth-first search (DFS) approach.

Recursive Approach:

1. Base Case:

• If the current node is null, return false.
• If the current node is a leaf node (both left and right children are null), check if the target equals the node's value.

2. Recursive Case:

• Recursively check the left and right subtrees with the updated target (target - root.data).

Steps:

1. Start from the root node.
2. Subtract the node’s value from the target sum.
3. Recursively check the left and right subtrees.
4. If either subtree returns true, return true.
5. If both subtrees return false, return false.

This approach ensures we explore all paths from the root to the leaves, checking their sums against the target.

Code Implementation:

/*
class Node{
    int data;
    Node left;
    Node right;
    Node(int data){
        this.data = data;
        left=null;
        right=null;
    }
}
*/

class Solution {
    
    boolean hasPathSum(Node root, int target) {
        
        if (root == null) return false;
        
        // If it's a leaf node, check if the current sum equals target
        if (root.left == null && root.right == null) {
            return target == root.data;
        }
        
        // Recur for left and right subtrees with the reduced target sum
        return hasPathSum(root.left, target - root.data) || hasPathSum(root.right, target - root.data);
    }
}

Complexity Analysis:

• Time Complexity: O(n) where n is the number of nodes in the tree. This is because we visit each node exactly once.
• Space Complexity: O(h) where h is the height of the tree. This is due to the recursive stack space, which in the worst case (skewed tree) could be O(n).