LeetCode-in-All

437. Path Sum III

Medium

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8

Output: 3

Explanation: The paths that sum to 8 are shown.

Example 2:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

Output: 3

Constraints:

• The number of nodes in the tree is in the range [0, 1000].
• -109 <= Node.val <= 109
• -1000 <= targetSum <= 1000

Solution

import com_github_leetcode.TreeNode;

/*
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    private int count = 0;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        helper(root, targetSum, 0);
        pathSum(root.left, targetSum);
        pathSum(root.right, targetSum);
        return count;
    }

    public void helper(TreeNode node, int targetSum, long currSum) {
        currSum += node.val;
        if (targetSum == currSum) {
            count++;
        }
        if (node.left != null) {
            helper(node.left, targetSum, currSum);
        }
        if (node.right != null) {
            helper(node.right, targetSum, currSum);
        }
    }
}

Time Complexity (Big O Time):

The time complexity of the program primarily depends on two recursive functions:

1. pathSum(TreeNode root, int targetSum): This function is the main driver of the calculation. It traverses the entire tree and calls the helper function for each node. In the worst case, it visits all nodes of the binary tree once. Therefore, its time complexity is O(n), where ‘n’ is the number of nodes in the tree.

2. helper(TreeNode node, int targetSum, long currSum): This function recursively explores all possible paths from a given node downward to its descendants. In the worst case, it traverses all paths from the root to leaf nodes. Since each node is visited once, the time complexity of this function is also O(n).

Combining both functions, the overall time complexity of the program is O(n), where ‘n’ is the number of nodes in the binary tree.

Space Complexity (Big O Space):

The space complexity of the program is primarily determined by the function call stack during recursion and the constant space used for variables:

1. Function Call Stack: The maximum depth of the call stack is the height of the binary tree. In the worst case, when the tree is skewed (completely unbalanced), the height can be ‘n,’ making the space complexity due to the call stack O(n).

2. Various integer variables used for iteration and intermediate calculations: These variables require constant space, O(1).

Combining these factors, the dominant factor in the space complexity is the call stack, which can grow up to O(n) in the worst case.

In summary, the provided program has a time complexity of O(n) and a space complexity of O(n), where ‘n’ is the number of nodes in the binary tree.

This site is open source. Improve this page.