Root to leaf path sum

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

Examples :

Input: tree = 1, target = 2
            /   \
          2     3
Output: false
Explanation: There is no root to leaf path with sum 2.

Input: tree = 1,  target = 4
            /   \
          2     3
Output: true
Explanation: The sum of path from leaf node 3 to root 1 is 4.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(height of tree)

Constraints:
1 ≤ number of nodes ≤ 10⁴
1 ≤ target ≤ 10⁶

Approach 01:

class Solution {
public:
    bool hasPathSum(Node* root, int targetSum) {
        if (root == nullptr) {
            return false;
        }
        if (root->left == nullptr && root->right == nullptr) {
            return targetSum == root->data;
        }
        int newTargetSum = targetSum - root->data;
        return hasPathSum(root->left, newTargetSum) || hasPathSum(root->right, newTargetSum);
    }
};

class Solution:
    def hasPathSum(self, root, targetSum):
        if root is None:
            return False
        if root.left is None and root.right is None:
            return targetSum == root.data
        newTargetSum = targetSum - root.data
        return self.hasPathSum(root.left, newTargetSum) or self.hasPathSum(root.right, newTargetSum)

Time Complexity

• Recursive Traversal:

  The function hasPathSum traverses each node in the tree exactly once. In the worst case, it visits all nodes.

• Overall Time Complexity:

  The overall time complexity is \( O(n) \), where \( n \) is the number of nodes in the tree.

Space Complexity

• Recursive Stack Space:

  The space complexity is determined by the maximum depth of the recursion stack. This depth is equal to the height of the tree.

• Overall Space Complexity:

  The overall space complexity is \( O(h) \), where \( h \) is the height of the tree. In the worst case, for a completely unbalanced tree, this can be \( O(n) \). For a balanced tree, the space complexity will be \( O(\log n) \).