import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/*
find paths in a binary search tree with nodes sum equal to K
*/
public class PathFindOne {
public static void main(String...arg) {
int[] values = {10, -5, -20, 3, -15, 7, 26, -9, 14};
System.out.println("Layer order");
BTree root = buildTree(values);
BTreePrinter.printNode(root);
System.out.println("the path with sum equal to -39 is:");
Set<List<BTree>> paths = new HashSet<>();
List<BTree> path = new ArrayList<>();
pathFind(root, paths, path, -39);
System.out.println(paths);
System.out.println("the path with sum equal to 15 is:");
paths = new HashSet<>();
path = new ArrayList<>();
pathFind(root, paths, path, 15);
System.out.println(paths);
System.out.println("the path with sum equal to 16 is:");
paths = new HashSet<>();
path = new ArrayList<>();
pathFind(root, paths, path, 16);
System.out.println(paths);
}
public static void pathFind(BTree root, Set<List<BTree>> paths, List<BTree> path, int total) {
if(root == null) return;
path.add(root);
if(root.left == null && root.right == null) {
int sum = 0;
for(BTree node: path) {
sum += node.value;
}
if(sum == total) {
List<BTree> list = new ArrayList<>();
list.addAll(path);
paths.add(list);
}
}
if(root.left != null) {
pathFind(root.left, paths, path, total);
}
if(root.right != null) {
pathFind(root.right, paths, path, total);
}
path.remove(path.size() - 1);
}
public static boolean contains(BTree root, int value) {
if(root == null) return false;
if(root.value == value) return true;
return contains(root.left, value) || contains(root.right, value);
}
//build a binary search tree
public static BTree buildTree(int[] values) {
BTree root = null;
for(int value : values) {
root = insert(root, value);
}
return root;
}
public static BTree insert(BTree root, int value) {
if(root == null) {
return new BTree(value, null, null);
}
if(value > root.value) {
root.right = insert(root.right, value);
return root;
}
if(value < root.value) {
root.left = insert(root.left, value);
return root;
}
root.value = value;
return root;
}
}
