437. Path Sum III LeetCode Solution

In this guide, you will get 437. Path Sum III LeetCode Solution with the best time and space complexity. The solution to Path Sum III problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Path Sum III solution in C++
Path Sum III solution in Java
Path Sum III solution in Python
Additional Resources

437. Path Sum III LeetCode Solution image

Problem Statement of Path Sum III

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

Complexity Analysis

Time Complexity: O(n\log n) \to O(n^2)
Space Complexity: O(\log n) \to O(n)

437. Path Sum III LeetCode Solution in C++

class Solution {
 public:
  int pathSum(TreeNode* root, int sum) {
    if (root == nullptr)
      return 0;
    return dfs(root, sum) +            //
           pathSum(root->left, sum) +  //
           pathSum(root->right, sum);
  }

 private:
  int dfs(TreeNode* root, int sum) {
    if (root == nullptr)
      return 0;
    return (sum == root->val) +                //
           dfs(root->left, sum - root->val) +  //
           dfs(root->right, sum - root->val);
  }
};
/* code provided by PROGIEZ */

437. Path Sum III LeetCode Solution in Java

class Solution {
  public int pathSum(TreeNode root, int sum) {
    if (root == null)
      return 0;
    return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
  }

  private int dfs(TreeNode root, int sum) {
    if (root == null)
      return 0;
    return (sum == root.val ? 1 : 0) +   //
        dfs(root.left, sum - root.val) + //
        dfs(root.right, sum - root.val);
  }
}
// code provided by PROGIEZ

437. Path Sum III LeetCode Solution in Python

class Solution:
  def pathSum(self, root: TreeNode | None, summ: int) -> int:
    if not root:
      return 0

    def dfs(root: TreeNode, summ: int) -> int:
      if not root:
        return 0
      return (int(summ == root.val) +
              dfs(root.left, summ - root.val) +
              dfs(root.right, summ - root.val))

    return (dfs(root, summ) +
            self.pathSum(root.left, summ) +
            self.pathSum(root.right, summ))
 # code by PROGIEZ