Problem 17 - Path Sum

Explore our archive for previous posts.

Question

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.

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:

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

• -1000 <= Node.val <= 1000

• -1000 <= targetSum <= 1000

Approach

This solution uses a recursive approach to traverse the binary tree and check if there exists a path from the root to a leaf node whose values sum up to the target sum.

The base cases handle empty subtrees and leaf nodes, while the recursive calls check the left and right child nodes by subtracting the current node's value from the target sum.

Solution

Solve it here

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        
        // Check if the current node is a leaf node and its value matches the target sum
        if (root.left == null && root.right == null && root.val == targetSum) {
            return true;
        }
        
        // Recursively check if the target sum can be reached by traversing the left or right subtree
        boolean left = hasPathSum(root.left, targetSum - root.val);
        boolean right = hasPathSum(root.right, targetSum - root.val);
        return left || right;
    }
}

Time and space complexity

Time Complexity: The time complexity of the above solution is O(n), where n is the number of nodes in the binary tree. This is because the solution recursively traverses each node exactly once.

Space Complexity: The space complexity of the solution is O(h), where h is the height of the binary tree. In the worst-case scenario, where the binary tree is skewed and resembles a linked list, the height can be equal to the number of nodes, resulting in a space complexity of O(n). However, in a balanced binary tree, the height is log(n), leading to a space complexity of O(log(n)). This space is used for the recursive call stack during the traversal process.