113. Path Sum II - LeetCode Fastest Solution

Hello Code Recipian! Welcome back to another article on LeetCode problem solutions. Today we will be solving LeetCode problem 113. Path Sum II.

This problem is an extension of 112. Path Sum which we have discussed in one of our other articles. If you have not yet checked it out we recommend you to go through that first before proceeding further in this article. It will help you build a solid foundation for solving this problem.

Problem Statement: Path Sum II

Given the root node of the binary tree and an integer targetSum, return all root to leaf paths in this tree such that, sum of these paths is equal to targetSum. Return paths as a list of node values.

A node in a tree that has no children is called a leaf node.

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 with targetSum = 22 highlighted in yellow: [5,4,11,2] and [5,8,4,5]

Example 2:

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

Output: []

Constraints:

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

• -1000 <= Node.val <= 1000

• -1000 <= targetSum <= 1000

Solution

Algorithm

Below is a step-by-step explanation for the working of the algorithm:

1. Initialization: Initialize a 2D array for storing our result. Let's call this result.

2. Call DFS function:

   Next we call the DFS function by passing the following parameters: node, targetSum, currPath, result.

   1. node represents the tree node. Initially when we call the DFS function, we pass the root node.

   2. targetSum is the target sum given in question.

   3. currPath array is used to keep track of the nodes in the current path, when we perform DFS traversal of the tree.

   4. result is used to store the result.

3. DFS Function:

   1. Base Case: The case for this recursive function is when we reach a null node. If we reach a null node, we stop further calls and return back to the caller.

   2. Subtract current node from target sum:

      Next we subtract the current node value from the given target sum. The reason behind doing this is that, if we reach a null node and if the targetSum after subtracting all the node values in that path is 0, it means we have found a path whose sum is equal to targetSum.

   3. Add to result if a path is found:

      Now we use the subtraction result from previous step to determine if we have found a path with targetSum. For a path to exist with the given targetSum, it must satisfy the following criteria:

      1. Current node must be a leaf node.

      2. Current targetSum value after subtraction must be equal 0.

      
      

      If we find any path that satisfies the above two criteria, we add the currPath to result array.

   4. Recursive calls to left and right child:

      Finally, we make recursive calls to left and right children of current node.

4. Return final result:

   Return the final result from the main function.

Simulation

Below is a pictorial depiction for the working of the algorithm:

Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide 

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Scala Solution

Rust Solution

Complexity Analysis

Time Complexity

DFS Traversal:

If n is the number of nodes in the given tree, in general DFS traversal of a tree takes O(n) time complexity.

Copying path values:

After finding a path we copy all currPath values to result, this requires a time complexity of O(H) for each path found, where H is the height of the given tree (O(H) since we are looking for a root to leaf path, so we will be copying only after we have reached the leaf node). For the given tree, if L is the number of leaf nodes, the overall time complexity for copying node values for every path found in the worst case is O(L * H).

Overall time complexity:

Considering the above factors :

1. For a balanced tree height H = log n, so the time complexity is O(n log n).

2. For a skewed tree, height is equal to the number of nodes in the tree, i.e. H = n, so time complexity if O(n²).

Space Complexity

For recursion:

To perform DFS using recursion, the space complexity for recursion stack is O(H). In the worst case (for skewed trees) this can be O(n).

Current path storage:

We use the currPath array to store the elements of current path during DFS. This space usage is directly proportional to the height of the tree and hence has a space complexity of O(H).

Storing the result:

We use the result 2D array to store our result. In the worst case, every leaf node might yield a valid path. So, the space complexity is O(L * H).

Overall space complexity:

Therefore the overall space complexity is O(n²) in the worst case for a skewed tree and O(n log n) in the average case for a balanced tree.

That brings us to the end of this article. We appreciate the time you have taken to read through it. If you have any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries.

If you enjoyed this article, please subscribe to our website and Youtube channel. Your support inspires us to bring out more such articles in future.

Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!

Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.