Print all k-sum paths in a binary tree - GeeksforGeeks
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, i.e. they need not be root node and leaf node; and negative numbers can also be there in the tree.
http://algorithms.tutorialhorizon.com/print-paths-in-binary-tree-with-sumx/
Given a binary tree and X, Print all the paths starting from root so that sum of all the nodes in path equals to a given number.
public void hasPath(Node root, int sum, String path){
if(root!=null){
if(root.data>sum){ // if root is greater than Sum required, return
return;
}else{
path+=" " + root.data; //add root to path
sum=sum-root.data; // update the required sum
if(sum==0){ //if sum required =0, means we have found the path
System.out.println(path);
}
hasPath(root.left, sum, path);
hasPath(root.right, sum, path);
}
}
http://www.geeksforgeeks.org/print-paths-root-specified-sum-binary-tree/
Read full article from Print all k-sum paths in a binary tree - GeeksforGeeks
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, i.e. they need not be root node and leaf node; and negative numbers can also be there in the tree.
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.
http://hevi.info/interviews/print-all-k-sum-paths-in-a-binary-tree/
My approach is basic, first think about a Tree with root only, if its value is equal to the given value then it is a solution. Now lets add a left and a right node. In this case as we go deeper on the tree we need to look for;
- starting from root, is the sum equals to the given value
- starting from the left is the sum equals to the given value and same for right
Hard part is collecting the correct path information.
The BST in solution hold lower values on the left and BST may contain negative values.
The complexity of my solution is O(n^2) hope it is not a concern for you
void
findSum(Integer originalSum, Integer sum,
List<List<Integer>> result, List<Integer> currentList,
Node node) {
if
(node ==
null
)
return
;
Integer nodeValue = node.value;
currentList.add(nodeValue);
if
(Objects.equals(sum, nodeValue)) {
List<Integer> resultL =
new
ArrayList(currentList);
result.add(resultL);
}
findSum(originalSum, originalSum, result,
new
ArrayList(), node.right);
findSum(originalSum, originalSum, result,
new
ArrayList(), node.left);
int
remaining = sum - nodeValue;
findSum(originalSum, remaining, result,
new
ArrayList(currentList), node.left);
findSum(originalSum, remaining, result,
new
ArrayList(currentList), node.right);
}
void
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);
}
http://algorithms.tutorialhorizon.com/print-paths-in-binary-tree-with-sumx/
Given a binary tree and X, Print all the paths starting from root so that sum of all the nodes in path equals to a given number.
public void hasPath(Node root, int sum, String path){
if(root!=null){
if(root.data>sum){ // if root is greater than Sum required, return
return;
}else{
path+=" " + root.data; //add root to path
sum=sum-root.data; // update the required sum
if(sum==0){ //if sum required =0, means we have found the path
System.out.println(path);
}
hasPath(root.left, sum, path);
hasPath(root.right, sum, path);
}
}
http://www.geeksforgeeks.org/print-paths-root-specified-sum-binary-tree/
oid
printPathsUtil(Node* curr_node,
int
sum,
int
sum_so_far, vector<
int
> &path)
{
if
(curr_node == NULL)
return
;
// add the current node's value
sum_so_far += curr_node->key;
// add the value to path
path.push_back(curr_node->key);
// print the required path
if
(sum_so_far == sum )
{
cout <<
"Path found: "
;
for
(
int
i=0; i<path.size(); i++)
cout << path[i] <<
" "
;
cout << endl;
}
// if left child exists
if
(curr_node->left != NULL)
printPathsUtil(curr_node->left, sum, sum_so_far, path);
// if right child exists
if
(curr_node->right != NULL)
printPathsUtil(curr_node->right, sum, sum_so_far, path);
// Remove last element from path
// and move back to parent
path.pop_back();
}