## Thursday, January 1, 2015

### An algorithm to print all paths which sum to a given value in a Binary Tree.

Q. You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. The path does not need to start or end at the root or a leaf.

Algorithm:

1. Start at the root or any other node (if a node other than root is given).
2. Check all nodes to left and to right recursively, pass the running sum and a string representation of the path downwards.
3. If the sum equals the required value, store that path or print it.
4. Continue down until you hit a null. (We don't quit when running sum matches the required value as there may be negative value nodes down in the path and then a positive one or there maybe zero value nodes down in the tree which IS a possible path).

Source:

```import java.util.ArrayList;
import java.util.List;

class Code{
class Node{
int value;
Node left, right;
Node(){}
Node(int value){this.value = value;}
Node(int value, Node left, Node right){
this.value = value;
this.left = left;
this.right = right;
}

@Override
public String toString(){
return Integer.toString(value);
}
}

Node root;

void helper(List<String> list, String s, Node origin, int sum, int value){
if(origin == null)return;
sum+=origin.value;
helper(list, s+" "+origin.toString(), origin.left, sum, value);
helper(list, s+" "+origin.toString(), origin.right, sum ,value);
}

void checkPaths(Node root, List<String> list, int value){
if(root == null)return;
helper(list,"", root, 0, value);
checkPaths(root.left, list, value);
checkPaths(root.right, list, value);
}

public void printPathsForValue(int value){
List<String> paths = new ArrayList<>();
checkPaths(root, paths, value);
System.out.println("Paths: \n"+paths);
}

public void buildCustomTree(){
root = new Node(1);
setChildren(root, 2, 3);
setChildren(root.left, 1, 2);
setChildren(root.left.right, null, 3);
setChildren(root.right, 1, 3);
setChildren(root.right.left, null, 4);
setChildren(root.right.right, null, 2);
setChildren(root.right.right.right, 1, null);

root = new Node(1);
setChildren(root, 2, 3);
setChildren(root.left, 1, 0);
setChildren(root.right, 1, 0);
setChildren(root.left.right, 0, 1);
setChildren(root.right, 1, 0);
setChildren(root.left.right, 0, 1);
setChildren(root.left.right.left, 1, null);
setChildren(root.right.left, 3, 2);
setChildren(root.right.left.right, 1, null);

//with -ve values as well
root = new Node(1);
setChildren(root, 2, 3);
setChildren(root.left, 1, 0);
setChildren(root.left.left, -1, null);
setChildren(root.left.left.left, 1, 2);
setChildren(root.left.left.left.right, -1, null);
setChildren(root.left.right, 0, 1);
setChildren(root.left.right.left, null, 1);
setChildren(root.right, 1, 0);
setChildren(root.right.left, 3, 2);
setChildren(root.right.left.right, 1, null);
}

private void setChildren(Node node, Integer left, Integer right){
if(left!=null)node.left = new Node(left);
if(right!=null)node.right = new Node(right);
}

public static void main(String[] args){
Code tree = new Code();
tree.buildCustomTree();
tree.printPathsForValue(4);
}
}```

Output:

Paths:
[ 1 2 1,  1 2 1 -1 1,  1 2 1 -1 2 -1,  1 2 0 0 1,  1 2 0 1,  1 3,  1 3 0,  2 1 -1 2,  3 1,  1 3,  1 2 1]

#### 1 comment:

1. package Tree;
import java.util.*;
public class Paths {
Node root;

public static void Listing(List l,Node root,String S,int N,int c){

if(root==null){System.out.print(0);}
S=S+Integer.toString(root.getContent());
c=c+root.getContent();
if(root.getleft()!=null){Listing(l,root.getleft(),S,N,c);}
if(root.getRight()!=null){Listing(l,root.getRight(),S,N,c);}

}

public static void main(String args[]){

Node d=new Node();
Node a=new Node();
Node b=new Node();
Node c=new Node();
Node f=new Node();
Node e=new Node();
Node g=new Node();
d.setcontent(9);
d.setleft(b);
d.setRight(f);

b.setcontent(5);
b.setleft(a);
b.setRight(c);

f.setcontent(12);
f.setleft(e);
f.setRight(g);

a.setcontent(2);
c.setcontent(7);
e.setcontent(10);
g.setcontent(15);