POTD Solutions | 20 Nov’ 23 | K Sum Paths
Welcome to the daily solutions of our PROBLEM OF THE DAY (POTD). We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of Binary Trees but will also help you build up problem-solving skills.
POTD 20 November: K Sum Paths
Given a binary tree and an integer K. Find the number of paths in the tree which have their sum equal to K. A path may start from any node and end at any node in the downward direction. Since the answer may be very large, compute it modulo 109+7.
Examples:
Input: k = 5
Root of below binary tree:
1
/ \
3 -1
/ \ / \
2 1 4 5
/ / \ \
1 1 2 6Output: No of paths with sum equals to 5 are: 8
3 2
3 1 1
1 3 1
4 1
1 -1 4 1
-1 4 2
5
1 -1 5Input: k = 3
1
/ \
2 -1
/ \ /
1 2 3
/ \
2 5Output: No of paths with sum equals to 3 are : 4
K Sum Paths using Backtracking and Hashing:
The idea is to use a recursive approach and an unordered map to track running sums. The count is increased when the running sum matches ‘k‘, and it also considers previously encountered sums from the map. The program then explores left and right subtrees, updating the map accordingly.
Step by Step approach:
- We will be using a unordered map which will be filled with various path sum.
- For every node we will check if current sum and root’s value equal to k or not. If the sum equals to k then increment the required answer by one.
- Then we will add all those path sum in map which differs from current sum+root->data value by a constant integer k.
- Then we will be inserting the current sum + root->data value in the map.
- We will recursively check for left and right subtrees of current root
- After the right subtree is also traversed we will remove the current sum + root->data value from the map so that it is not taken into consideration in further traversals of other nodes other than the current root’s
Below is the implementation of the above approach:
C++
class Solution{ public : // Function to backtrack the tree path and // add each path sum in the unordered map void k_paths(Node* root, int k, unordered_map< int , int >& p, int sum, int &res) { // If root is not null if (root) { // If root value and previous sum equal // to k then increase the count if (sum + root->data == k) res++; // Add those values also which differs // by the current sum and root data by k res += p[sum + root->data - k]; // Insert the sum + root value in the map p[sum + root->data]++; // Move to left and right trees k_paths(root->left, k, p, sum + root->data, res); k_paths(root->right, k, p, sum + root->data, res); // remove the sum + root->data value from the // map if they are n not required further or // they do not sum up to k in any way p[sum + root->data]--; } } // Function to print the count // of paths with sum equals to k int sumK(Node *root, int k) { // To store the required answer int res = 0; // To store the sum unordered_map< int , int > p; // Function call k_paths(root, k, p, 0, res); // Return the required answer return res; } }; |
Java
class Solution { void kPaths(Node root, int k, Map<Integer, Integer> p, int sum, int [] res) { // If root is not null if (root != null ) { // If root value and previous sum equal // to k then increase the count if (sum + root.data == k) res[ 0 ]++; // Add those values also which differs // by the current sum and root data by k res[ 0 ] += p.getOrDefault(sum + root.data - k, 0 ); // Insert the sum + root value in the map p.put(sum + root.data, p.getOrDefault(sum + root.data, 0 ) + 1 ); // Move to left and right trees kPaths(root.left, k, p, sum + root.data, res); kPaths(root.right, k, p, sum + root.data, res); // remove the sum + root.data value from the // map if they are not required further or // they do not sum up to k in any way p.put(sum + root.data, p.get(sum + root.data) - 1 ); } } // Function to print the count // of paths with sum equals to k public int sumK(Node root, int k) { // To store the required answer int [] res = { 0 }; // To store the sum Map<Integer, Integer> p = new HashMap<>(); // Function call kPaths(root, k, p, 0 , res); // Return the required answer return res[ 0 ]; } } |
Python3
class Solution: # Function to backtrack the tree path and # add each path sum in the dictionary def k_paths( self , root, k, p, sum , res): # If root is not None if root: # If root value and previous sum equal # to k then increase the count if sum + root.data = = k: res[ 0 ] + = 1 # Add those values also which differ # by the current sum and root data by k res[ 0 ] + = p.get( sum + root.data - k, 0 ) # Insert the sum + root value in the dictionary p[ sum + root.data] = p.get( sum + root.data, 0 ) + 1 # Move to left and right trees self .k_paths(root.left, k, p, sum + root.data, res) self .k_paths(root.right, k, p, sum + root.data, res) # Remove the sum + root.data value from the # dictionary if they are not required further or # they do not sum up to k in any way p[ sum + root.data] - = 1 if p[ sum + root.data] = = 0 : del p[ sum + root.data] def sumK( self ,root,k): # To store the required answer res = [ 0 ] # To store the sum p = {} # Function call self .k_paths(root, k, p, 0 , res) # Return the required answer return res[ 0 ] |
Time Complexity: O(N), where N is the number of nodes in the tree
Auxiliary Space: O(N), where N is the number of nodes in the tree