113. Path Sum II LeetCode Solution

Last updated: February 14, 2025

In this guide, you will get 113. Path Sum II LeetCode Solution with the best time and space complexity. The solution to Path Sum II 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 II solution in C++
Path Sum II solution in Java
Path Sum II solution in Python
Additional Resources

113. Path Sum II LeetCode Solution image

Problem Statement of Path Sum II

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: []

Example 3:

Input: root = [1,2], targetSum = 0
Output: []

Constraints:

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

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

113. Path Sum II LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> pathSum(TreeNode* root, int sum) {
    vector<vector<int>> ans;
    dfs(root, sum, {}, ans);
    return ans;
  }

 private:
  void dfs(TreeNode* root, int sum, vector<int>&& path,
           vector<vector<int>>& ans) {
    if (root == nullptr)
      return;
    if (root->val == sum && root->left == nullptr && root->right == nullptr) {
      path.push_back(root->val);
      ans.push_back(path);
      path.pop_back();
      return;
    }

    path.push_back(root->val);
    dfs(root->left, sum - root->val, std::move(path), ans);
    dfs(root->right, sum - root->val, std::move(path), ans);
    path.pop_back();
  }
};
/* code provided by PROGIEZ */

113. Path Sum II LeetCode Solution in Java

class Solution {
  public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> ans = new ArrayList<>();
    dfs(root, sum, new ArrayList<>(), ans);
    return ans;
  }

  private void dfs(TreeNode root, int sum, List<Integer> path, List<List<Integer>> ans) {
    if (root == null)
      return;
    if (root.val == sum && root.left == null && root.right == null) {
      path.add(root.val);
      ans.add(new ArrayList<>(path));
      path.remove(path.size() - 1);
      return;
    }

    path.add(root.val);
    dfs(root.left, sum - root.val, path, ans);
    dfs(root.right, sum - root.val, path, ans);
    path.remove(path.size() - 1);
  }
}
// code provided by PROGIEZ

113. Path Sum II LeetCode Solution in Python

class Solution:
  def pathSum(self, root: TreeNode, summ: int) -> list[list[int]]:
    ans = []

    def dfs(root: TreeNode, summ: int, path: list[int]) -> None:
      if not root:
        return
      if root.val == summ and not root.left and not root.right:
        ans.append(path + [root.val])
        return

      dfs(root.left, summ - root.val, path + [root.val])
      dfs(root.right, summ - root.val, path + [root.val])

    dfs(root, summ, [])
    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents