DEV Community

Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

LeetCode - Path Sum II

Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/path-sum-ii

Example 1:

Container

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
Enter fullscreen mode Exit fullscreen mode

Example 2:

Container

Input: root = [1, 2, 3], targetSum = 5
Output: []
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: root = [1, 2], targetSum = 0
Output: []
Enter fullscreen mode Exit fullscreen mode

Constraints:

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

Explanation

The problem is similar to our previous blog post Path Sum. We will use the same algorithm flow here, but we will also store the tree node values in an array.

Let's check the algorithm first.

- set 2D array vector<vector<int>> result
      1D array vector<int> current

- getPathSum(root, result, current, targetSum)

- return result

// getPathSum function
- if root == NULL
  - return

- if root->val == targetSum && root->left == NULL && root->right == NULL
  - current.push_back(root->val)
  - result.push_back(current)
  - return

- set remainingTargetSum = targetSum - root->val
- current.push_back(root->val)

- getPathSum(root->left, result, current, remainingTargetSum)
- getPathSum(root->right, result, current, remainingTargetSum)

- return
Enter fullscreen mode Exit fullscreen mode

Let's check our algorithm in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    void getPathSum(TreeNode* root, vector<vector<int>> &result, vector<int> current, int targetSum) {
        if(root == NULL) {
            return;
        }

        if(root->val == targetSum && root->left == NULL && root->right == NULL) {
            current.push_back(root->val);
            result.push_back(current);
            return;
        }

        int remainingTargetSum = targetSum - root->val;
        current.push_back(root->val);

        getPathSum(root->left, result, current, remainingTargetSum);
        getPathSum(root->right, result, current, remainingTargetSum);

        return;
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> result;
        vector<int> current;

        getPathSum(root, result, current, targetSum);

        return result;
    }
};
Enter fullscreen mode Exit fullscreen mode

Golang solution

func getPathSum(root *TreeNode, result *[][]int, current []int, targetSum int) {
    if root == nil {
        return
    }

    if root.Val == targetSum && root.Left == nil && root.Right == nil {
        current = append(current, root.Val)
        *result = append(*result, append([]int(nil),current...))
        return
    }

    remainingTargetSum := targetSum - root.Val

    current = append(current, root.Val)

    getPathSum(root.Left, result, current, remainingTargetSum)
    getPathSum(root.Right, result, current, remainingTargetSum)

    return
}

func pathSum(root *TreeNode, targetSum int) [][]int {
    result := [][]int{}
    current := []int{}

    getPathSum(root, &result, current, targetSum)

    return result
}
Enter fullscreen mode Exit fullscreen mode

Javascript solution

var pathSum = function(root, targetSum) {
    let result = [];

    var getPathSum = function(root, current, targetSum) {
        if(root === null) {
            return;
        }

        if(root.val === targetSum && root.left === null && root.right === null) {
            result.push([...current, root.val]);
            return;
        }

        let remainingTargetSum = targetSum - root.val;

        getPathSum(root.left, [...current, root.val], remainingTargetSum);
        getPathSum(root.right, [...current, root.val], remainingTargetSum);

        return;
    }

    getPathSum(root, [], targetSum);

    return result;
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm for Example 1.

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

Step 1: initialize vector<vector<int>> result;
        vector<int> current;

Step 2: getPathSum(root, result, current, targetSum)
        getPathSum(root, [[]], [], 22)
        the root is at 5

// getPathSum
Step 3: if root == NULL
          false

        if root->val == targetSum && root->left == NULL && root->right == NULL
           5 == 22
           false

           remainingTargetSum = targetSum - root->val
                              = 22 - 5
                              = 17

           current.push_back(root->val)
           current = [5]

           getPathSum(root->left, result, current, remainingTargetSum)
           getPathSum(4, [[]], [5], 17)

Step 4: if root == NULL
          the root is at 4
          false

        if root->val == targetSum && root->left == NULL && root->right == NULL
           4 == 17
           false

           remainingTargetSum = targetSum - root->val
                              = 17 - 4
                              = 13

           current.push_back(root->val)
           current = [5, 4]

           getPathSum(root->left, result, current, remainingTargetSum)
           getPathSum(11, [[]], [5, 4], 13)

Step 5: if root == NULL
          the root is at 11
          false

        if root->val == targetSum && root->left == NULL && root->right == NULL
           11 == 13
           false

           remainingTargetSum = targetSum - root->val
                              = 13 - 11
                              = 2

           current.push_back(root->val)
           current = [5, 4, 11]

           getPathSum(root->left, result, current, remainingTargetSum)
           getPathSum(7, [[]], [5, 4, 11], 2)

Step 6: if root == NULL
          the root is at 7
          false

        if root->val == targetSum && root->left == NULL && root->right == NULL
           7 == 2
           false

           remainingTargetSum = targetSum - root->val
                              = 2 - 7
                              = -5

           current.push_back(root->val)
           current = [5, 4, 11, 7]

           getPathSum(root->left, result, current, remainingTargetSum)
           getPathSum(NULL, [[]], [5, 4, 11, 7], -5)

Step 7: if root == NULL
          the root is NULL
          true

          We backtrack to step 6 and continue

Step 8: getPathSum(root->right, result, current, remainingTargetSum)
        getPathSum(2, [[]], [5, 4, 11], 2)

Step 9: if root == NULL
          the root is at 2
          false

        if root->val == targetSum && root->left == NULL && root->right == NULL
           2 == 2 && root->left == NULL && root->right == NULL
           true

           current.push_back(root->val)
           current = [5, 4, 11, 2]

           result.push_back(current)
           result = [[5, 4, 11, 2]]

           return

        We backtrack to step 4 and continue

Step 10: getPathSum(root->right, result, current, remainingTargetSum)
         getPathSum(NULL, [[5, 4, 11, 2]], [5, 4], 13)

Step 11: if root == NULL
          the root is NULL
          true

          We backtrack to step 3 and continue

Step 12: getPathSum(root->right, result, current, remainingTargetSum)
         getPathSum(8, [[5, 4, 11, 2]], [5], 17)

Step 13: if root == NULL
          the root is at 8
          false

         if root->val == targetSum && root->left == NULL && root->right == NULL
            8 == 17
            false

         remainingTargetSum = targetSum - root->val
                              = 17 - 8
                              = 9

         current.push_back(root->val)
         current = [5, 8]

         getPathSum(root->left, result, current, remainingTargetSum)
         getPathSum(13, [[5, 4, 11, 2]], [5, 8], 9)

Step 14: if root == NULL
          the root is at 13
          false

         if root->val == targetSum && root->left == NULL && root->right == NULL
            13 == 9
            false

         remainingTargetSum = targetSum - root->val
                              = 9 - 13
                              = -4

         current.push_back(root->val)
         current = [5, 8, 13]

         getPathSum(root->left, result, current, remainingTargetSum)
         getPathSum(NULL, [[5, 4, 11, 2]], [5, 8, 13], -4)

Step 15: if root == NULL
          the root is NULL
          true

          We backtrack to step 14 and continue

Step 16: getPathSum(root->right, result, current, remainingTargetSum)
         getPathSum(NULL, [[5, 4, 11, 2]], [5, 8, 13], -4)

Step 17: if root == NULL
          the root is NULL
          true

          We backtrack to step 13 and continue

Step 18: getPathSum(root->right, result, current, remainingTargetSum)
         getPathSum(4, [[5, 4, 11, 2]], [5, 8], 9)

Step 19: if root == NULL
          the root is at 4
          false

         if root->val == targetSum && root->left == NULL && root->right == NULL
            4 == 9
            false

         remainingTargetSum = targetSum - root->val
                              = 9 - 4
                              = 5

         current.push_back(root->val)
         current = [5, 8, 4]

         getPathSum(root->left, result, current, remainingTargetSum)
         getPathSum(5, [[5, 4, 11, 2]], [5, 8, 4], 5)

Step 20: if root == NULL
          the root is at 5
          false

         if root->val == targetSum && root->left == NULL && root->right == NULL
            5 == 5
            true

            current.push_back(root->val)
            current = [5, 8, 4, 5]

            result.push_back(current)
            result = [[5, 4, 11, 2], [5, 8, 4, 5]]

            return

        We backtrack to step 19 and continue

Once the last rightmost lead node is processed
we return the result

The answer is [[5, 4, 11, 2], [5, 8, 4, 5]].
Enter fullscreen mode Exit fullscreen mode

Top comments (0)