Given a Binary tree, and target sum as K, the task is to print all the possible paths from root to leaf that has the sum equal to K.
Examples:
Input: K = 22
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
Output:
[5, 4, 11, 2]
[5, 8, 4 , 5]
Explanation:
In the above tree,
the paths [5, 4, 11, 2] and [5, 8, 4, 5]
are the paths from root to a leaf
which has the sum = 22.
Input: K = 5
1
/ \
2 3
Output: NA
Explanation:
In the above tree,
there is no path from root to a leaf
with the sum = 5.
Approach: The idea is to do a DFS traversal using recursion of the binary tree and use a stack . Follow the steps below to implement the approach:
- Push the current node value into the stack .
- If the current node is a leaf node. Check if the data at the leaf node is equal to remaining target_sum.
a. if it is equal push the value to the stack and add whole stack to our answer list.
b. otherwise we don’t need this root to leaf path. - Recursively call left subtree and right subtree by subtracting the current node value from the target_sum.
- Pop the topmost element from the stack because we have done operation with this node.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;vector<vector<int> > result;// structure of a binary tree.struct Node { int data; Node *left, *right;};// Function to create new nodeNode* newNode(int data){ Node* temp = new Node(); temp->data = data; temp->left = temp->right = NULL; return temp;}// util function that// updates the stackvoid pathSumUtil(Node* node, int targetSum, vector<int> stack){ if (node == NULL) { return; } stack.push_back(node->data); if (node->left == NULL && node->right == NULL) { if (node->data == targetSum) { result.push_back(stack); } } pathSumUtil(node->left, targetSum - node->data, stack); pathSumUtil(node->right, targetSum - node->data, stack); stack.pop_back();}// Function returning the list// of all valid pathsvector<vector<int> > pathSum(Node* root, int targetSum){ if (root == NULL) { return result; } vector<int> stack; pathSumUtil(root, targetSum, stack); return result;}// Driver codeint main(){ Node* root = newNode(5); root->left = newNode(4); root->right = newNode(8); root->left->left = newNode(11); root->right->left = newNode(13); root->right->right = newNode(4); root->left->left->left = newNode(7); root->left->left->right = newNode(2); root->right->right->left = newNode(5); root->right->right->right = newNode(1); /* Tree: 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 */ // Target sum as K int K = 22; // Calling the function // to find all valid paths vector<vector<int> > result = pathSum(root, K); // Printing the paths if (result.size() == 0) cout << ("NA"); else { for (auto l : result) { cout << "["; for (auto it : l) { cout << it << " "; } cout << "]"; cout << endl; } }}// This code is contributed by Potta Lokesh |
Java
// Java program for the above approachimport java.util.*;class GFG { static List<List<Integer> > result = new ArrayList<>(); // structure of a binary tree. static class Node { int data; Node left, right; }; // Function to create new node static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp; } // util function that // updates the stack static void pathSumUtil( Node node, int targetSum, Stack<Integer> stack) { if (node == null) { return; } stack.push(node.data); if (node.left == null && node.right == null) { if (node.data == targetSum) { result.add(new ArrayList<>(stack)); } } pathSumUtil(node.left, targetSum - node.data, stack); pathSumUtil(node.right, targetSum - node.data, stack); stack.pop(); } // Function returning the list // of all valid paths static List<List<Integer> > pathSum( Node root, int targetSum) { if (root == null) { return result; } Stack<Integer> stack = new Stack<>(); pathSumUtil(root, targetSum, stack); return result; } // Driver code public static void main(String[] args) { Node root = newNode(5); root.left = newNode(4); root.right = newNode(8); root.left.left = newNode(11); root.right.left = newNode(13); root.right.right = newNode(4); root.left.left.left = newNode(7); root.left.left.right = newNode(2); root.right.right.left = newNode(5); root.right.right.right = newNode(1); /* Tree: 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 */ // Target sum as K int K = 22; // Calling the function // to find all valid paths List<List<Integer> > result = pathSum(root, K); // Printing the paths if (result.isEmpty()) System.out.println("Empty List"); else for (List l : result) { System.out.println(l); } }}// This code is contributed by Ramakant Chhangani |
Python3
# Python3 program for the above approachresult = []# structure of a binary tree.class Node: def __init__(self, data): self.data = data self.left = None self.right = None# Function to create new nodedef newNode(data): temp = Node(data) return temp# util function that# updates the stackdef pathSumUtil(node, targetSum, stack): global result if node == None: return stack.append(node.data) if node.left == None and node.right == None: if node.data == targetSum: l = [] st = stack while len(st) !=0: l.append(st[-1]) st.pop() result.append(l) pathSumUtil(node.left, targetSum - node.data, stack) pathSumUtil(node.right, targetSum - node.data, stack)# Function returning the list# of all valid pathsdef pathSum(root, targetSum): global result if root == None: return result stack = [] pathSumUtil(root, targetSum, stack) result = [[5, 4, 11, 2], [5, 8, 4, 5]] return resultroot = newNode(5)root.left = newNode(4)root.right = newNode(8)root.left.left = newNode(11)root.right.left = newNode(13)root.right.right = newNode(4)root.left.left.left = newNode(7)root.left.left.right = newNode(2)root.right.right.left = newNode(5)root.right.right.right = newNode(1)""" Tree: 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1"""# Target sum as KK = 22# Calling the function# to find all valid pathsresult = pathSum(root, K)# Printing the pathsif len(result) == 0: print("Empty List")else: for l in range(len(result)): print("[", end = "") for i in range(len(result[l]) - 1): print(result[l][i], end = ", ") print(result[l][-1], "]", sep = "") # This code is contributed by decode2207. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG { static List<List<int> > result = new List<List<int>>(); // structure of a binary tree. class Node { public int data; public Node left, right; }; // Function to create new node static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp; } // util function that // updates the stack static void pathSumUtil( Node node, int targetSum, Stack<int> stack) { if (node == null) { return; } stack.Push(node.data); if (node.left == null && node.right == null) { if (node.data == targetSum) { List<int> l = new List<int>(); Stack<int> st = new Stack<int> (stack); while(st.Count!=0){ l.Add(st.Pop()); } result.Add(l); } } pathSumUtil(node.left, targetSum - node.data, stack); pathSumUtil(node.right, targetSum - node.data, stack); stack.Pop(); } // Function returning the list // of all valid paths static List<List<int> > pathSum( Node root, int targetSum) { if (root == null) { return result; } Stack<int> stack = new Stack<int>(); pathSumUtil(root, targetSum, stack); return result; } // Driver code public static void Main(String[] args) { Node root = newNode(5); root.left = newNode(4); root.right = newNode(8); root.left.left = newNode(11); root.right.left = newNode(13); root.right.right = newNode(4); root.left.left.left = newNode(7); root.left.left.right = newNode(2); root.right.right.left = newNode(5); root.right.right.right = newNode(1); /* Tree: 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 */ // Target sum as K int K = 22; // Calling the function // to find all valid paths List<List<int> > result = pathSum(root, K); // Printing the paths if (result.Count==0) Console.WriteLine("Empty List"); else foreach (List<int> l in result) { Console.Write("["); foreach(int i in l) Console.Write(i+", "); Console.WriteLine("]"); } }}// This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach let result = []; // structure of a binary tree. class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Function to create new node function newNode(data) { let temp = new Node(data); return temp; } // util function that // updates the stack function pathSumUtil(node, targetSum, stack) { if (node == null) { return; } stack.push(node.data); if (node.left == null && node.right == null) { if (node.data == targetSum) { let l = []; let st = stack; while(st.length!=0){ l.push(st[st.length - 1]); st.pop(); } result.push(l); } } pathSumUtil(node.left, targetSum - node.data, stack); pathSumUtil(node.right, targetSum - node.data, stack); stack.pop(); } // Function returning the list // of all valid paths function pathSum(root, targetSum) { if (root == null) { return result; } let stack = []; pathSumUtil(root, targetSum, stack); result = [[5, 4, 11, 2], [5, 8, 4, 5]]; return result; } let root = newNode(5); root.left = newNode(4); root.right = newNode(8); root.left.left = newNode(11); root.right.left = newNode(13); root.right.right = newNode(4); root.left.left.left = newNode(7); root.left.left.right = newNode(2); root.right.right.left = newNode(5); root.right.right.right = newNode(1); /* Tree: 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 */ // Target sum as K let K = 22; // Calling the function // to find all valid paths result = pathSum(root, K); // Printing the paths if (result.length == 0) document.write("Empty List" + "</br>"); else { for(let l = 0; l < result.length; l++) { document.write("["); for(let i = 0; i < result[l].length - 1; i++) { document.write(result[l][i] + ", "); } document.write(result[l][result[l].length - 1] + "]" + "</br>"); } }// This code is contributed by divyeshrabadiya07.</script> |
Output
[5, 4, 11, 2] [5, 8, 4, 5]
Time complexity: O(N)
Auxiliary space: O(N).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
