A binary tree and a number k are given. Print every path in the tree with sum of the nodes in the path as k.
A path can start from any node and end at any node and must be downward only, i.e. they need not be root node and leaf node; and negative numbers can also be there in the tree.
Examples:
Input : k = 5
Root of below binary tree:
1
/ \
3 -1
/ \ / \
2 1 4 5
/ / \ \
1 1 2 6
Output :
3 2
3 1 1
1 3 1
4 1
1 -1 4 1
-1 4 2
5
1 -1 5
Source : Amazon Interview Experience Set-323
Kindly note that this problem is significantly different from finding k-sum path from root to leaves. Here each node can be treated as root, hence the path can start and end at any node.
Approach:
The basic idea to solve the problem is to do a preorder traversal of the given tree. We also need a container (vector) to keep track of the path that led to that node. At each node we check if there are any path that sums to k, if any we print the path and proceed recursively to print each path.
Code:
Below is the implementation of the same.
C++
// C++ program to print all paths with sum k.#include <bits/stdc++.h>using namespace std;// utility function to print contents of// a vector from index i to it's endvoid printVector(const vector<int>& v, int i){ for (int j = i; j < v.size(); j++) cout << v[j] << " "; cout << endl;}// binary tree nodestruct Node { int data; Node *left, *right; Node(int x) { data = x; left = right = NULL; }};// This function prints all paths that have sum kvoid printKPathUtil(Node* root, vector<int>& path, int k){ // empty node if (!root) return; // add current node to the path path.push_back(root->data); // check if there's any k sum path // in the left sub-tree. printKPathUtil(root->left, path, k); // check if there's any k sum path // in the right sub-tree. printKPathUtil(root->right, path, k); // check if there's any k sum path that // terminates at this node // Traverse the entire path as // there can be negative elements too int f = 0; for (int j = path.size() - 1; j >= 0; j--) { f += path[j]; // If path sum is k, print the path if (f == k) printVector(path, j); } // Remove the current element from the path path.pop_back();}// A wrapper over printKPathUtil()void printKPath(Node* root, int k){ vector<int> path; printKPathUtil(root, path, k);}// Driver codeint main(){ Node* root = new Node(1); root->left = new Node(3); root->left->left = new Node(2); root->left->right = new Node(1); root->left->right->left = new Node(1); root->right = new Node(-1); root->right->left = new Node(4); root->right->left->left = new Node(1); root->right->left->right = new Node(2); root->right->right = new Node(5); root->right->right->right = new Node(2); int k = 5; printKPath(root, k); return 0;} |
Java
// Java program to print all paths with sum k.import java.util.*;class GFG { // utility function to print contents of // a vector from index i to it's end static void printVector(Vector<Integer> v, int i) { for (int j = i; j < v.size(); j++) System.out.print(v.get(j) + " "); System.out.println(); } // binary tree node static class Node { int data; Node left, right; Node(int x) { data = x; left = right = null; } }; static Vector<Integer> path = new Vector<Integer>(); // This function prints all paths that have sum k static void printKPathUtil(Node root, int k) { // empty node if (root == null) return; // add current node to the path path.add(root.data); // check if there's any k sum path // in the left sub-tree. printKPathUtil(root.left, k); // check if there's any k sum path // in the right sub-tree. printKPathUtil(root.right, k); // check if there's any k sum path that // terminates at this node // Traverse the entire path as // there can be negative elements too int f = 0; for (int j = path.size() - 1; j >= 0; j--) { f += path.get(j); // If path sum is k, print the path if (f == k) printVector(path, j); } // Remove the current element from the path path.remove(path.size() - 1); } // A wrapper over printKPathUtil() static void printKPath(Node root, int k) { path = new Vector<Integer>(); printKPathUtil(root, k); } // Driver code public static void main(String args[]) { Node root = new Node(1); root.left = new Node(3); root.left.left = new Node(2); root.left.right = new Node(1); root.left.right.left = new Node(1); root.right = new Node(-1); root.right.left = new Node(4); root.right.left.left = new Node(1); root.right.left.right = new Node(2); root.right.right = new Node(5); root.right.right.right = new Node(2); int k = 5; printKPath(root, k); }}// This code is contributed by Arnab Kundu |
Python3
# Python3 program to print all paths# with sum k# utility function to print contents of# a vector from index i to it's enddef printVector(v, i): for j in range(i, len(v)): print(v[j], end=" ") print()# Binary Tree Node""" utility that allocates a newNode with the given key """class newNode: # Construct to create a newNode def __init__(self, key): self.data = key self.left = None self.right = None# This function prints all paths# that have sum kdef printKPathUtil(root, path, k): # empty node if (not root): return # add current node to the path path.append(root.data) # check if there's any k sum path # in the left sub-tree. printKPathUtil(root.left, path, k) # check if there's any k sum path # in the right sub-tree. printKPathUtil(root.right, path, k) # check if there's any k sum path that # terminates at this node # Traverse the entire path as # there can be negative elements too f = 0 for j in range(len(path) - 1, -1, -1): f += path[j] # If path sum is k, print the path if (f == k): printVector(path, j) # Remove the current element # from the path path.pop(-1)# A wrapper over printKPathUtil()def printKPath(root, k): path = [] printKPathUtil(root, path, k)# Driver Codeif __name__ == '__main__': root = newNode(1) root.left = newNode(3) root.left.left = newNode(2) root.left.right = newNode(1) root.left.right.left = newNode(1) root.right = newNode(-1) root.right.left = newNode(4) root.right.left.left = newNode(1) root.right.left.right = newNode(2) root.right.right = newNode(5) root.right.right.right = newNode(2) k = 5 printKPath(root, k)# This code is contributed by# Shubham Singh(SHUBHAMSINGH10) |
C#
// C# program to print all paths with sum k.using System;using System.Collections.Generic;class GFG { // utility function to print contents of // a vector from index i to it's end static void printList(List<int> v, int i) { for (int j = i; j < v.Count; j++) Console.Write(v[j] + " "); Console.WriteLine(); } // binary tree node public class Node { public int data; public Node left, right; public Node(int x) { data = x; left = right = null; } }; static List<int> path = new List<int>(); // This function prints all paths that have sum k static void printKPathUtil(Node root, int k) { // empty node if (root == null) return; // add current node to the path path.Add(root.data); // check if there's any k sum path // in the left sub-tree. printKPathUtil(root.left, k); // check if there's any k sum path // in the right sub-tree. printKPathUtil(root.right, k); // check if there's any k sum path that // terminates at this node // Traverse the entire path as // there can be negative elements too int f = 0; for (int j = path.Count - 1; j >= 0; j--) { f += path[j]; // If path sum is k, print the path if (f == k) printList(path, j); } // Remove the current element from the path path.RemoveAt(path.Count - 1); } // A wrapper over printKPathUtil() static void printKPath(Node root, int k) { path = new List<int>(); printKPathUtil(root, k); } // Driver code public static void Main(String[] args) { Node root = new Node(1); root.left = new Node(3); root.left.left = new Node(2); root.left.right = new Node(1); root.left.right.left = new Node(1); root.right = new Node(-1); root.right.left = new Node(4); root.right.left.left = new Node(1); root.right.left.right = new Node(2); root.right.right = new Node(5); root.right.right.right = new Node(2); int k = 5; printKPath(root, k); }}// This code is contributed by PrinciRaj1992 |
Javascript
// Tree node class for Binary Tree// representationclass Node { constructor(data) { this.data = data; this.left = this.right = null; }}function printPathUtil(node, k, path_arr, all_path_arr) { if (node == null) { return; } let p1 = node.data.toString(); let p2 = ''; if (path_arr.length > 0) { p2 = path_arr + ',' + p1; } else { p2 = p1; } if (node.data == k) { all_path_arr.add(p1); } let sum = 0; let p2_arr = p2.split(','); for (let i = 0; i < p2_arr.length; i++) { sum = sum + Number(p2_arr[i]); } if (sum == k) { all_path_arr.add(p2); } printPathUtil(node.left, k, p1, all_path_arr) printPathUtil(node.left, k, p2, all_path_arr) printPathUtil(node.right, k, p1, all_path_arr) printPathUtil(node.right, k, p2, all_path_arr)}function printKPath(root, k) { let all_path_arr = new Set(); printPathUtil(root, k, '', all_path_arr); return all_path_arr;}function printPaths(paths) { for (let data of paths) { document.write(data.replaceAll(',', ' ')); document.write('<br>'); }}// Driver codelet root = new Node(1);root.left = new Node(3);root.left.left = new Node(2);root.left.right = new Node(1);root.left.right.left = new Node(1);root.right = new Node(-1);root.right.left = new Node(4);root.right.left.left = new Node(1);root.right.left.right = new Node(2);root.right.right = new Node(5);root.right.right.right = new Node(2);let k = 5;printPaths(printKPath(root, k));// This code is contributed by gaurav2146 |
Output
3 2 3 1 1 1 3 1 4 1 1 -1 4 1 -1 4 2 5 1 -1 5
Time complexity: O(N^2), where N is the number of nodes in the binary tree. This is because for each node, we traverse the entire path (up to N nodes) to check if there exists a path with a sum equal to k.
Auxiliary space: O(N) because in the worst case, the path vector can store up to N nodes. Additionally, the recursive calls consume stack space proportional to the height of the tree, which can be at most N in the case of a skewed tree.
This article is contributed by Ashutosh Kumar If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
