## Print all paths in a binary tree which sum up to a value

You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree – it does not have to start at the root.

My initial thoughts:
Two recursive structures:

1. Recursively traverse every node in the tree.
2. Rooted at a single node $r$ with value $r$.value(), recursively find paths that contains value – $r$.value().

My initial codes:

```	public static void printAllPathsSumUpTo(BinaryTreeNode<Integer> root,
int value) {
printRecursively(root, value, new String());
if (root != null) {
printAllPathsSumUpTo(root.getLeft(), value);
printAllPathsSumUpTo(root.getRight(), value);
}
}

public static void printRecursively(BinaryTreeNode<Integer> root,
int value, String str) {
if (root == null)
return;
else if (root.getValue() == value) {
System.out.println((str.isEmpty() ? "" : " -> ") + root);
} else {
printRecursively(root.getLeft(), value - root.getValue(),
(str.isEmpty() ? "" : " -> ") + root);
printRecursively(root.getRight(), value - root.getValue(),
(str.isEmpty() ? "" : " -> ") + root);
}
}

Problems after running:
INPUT: BST built from sorted array 6 29 35 48 51 56 68 73 79 96 and value = 35.
EXPECTED OUTPUT: 29 -> 6 and 35
OUTPUT:  -> 6 and 35.
CORRECTION: Change highlighted line 15, 18 and 20 to:
(str.isEmpty() ? "" : str + " -> ")

Solution:
public static void findSum(BinaryTreeNode<Integer> head, int sum,
ArrayList<Integer> buffer, int level) {
return;
int tmp = sum;
for (int i = level; i > -1; i--) {
tmp -= buffer.get(i);
if (tmp == 0)
print(buffer, i, level);
}
ArrayList<Integer> c1 = (ArrayList<Integer>) buffer.clone();
ArrayList<Integer> c2 = (ArrayList<Integer>) buffer.clone();
findSum(head.getLeft(), sum, c1, level + 1);
findSum(head.getRight(), sum, c2, level + 1);
}

public static void print(ArrayList<Integer> buffer, int level, int i2) {
for (int i = level; i <= i2; i++) {
System.out.print(buffer.get(i) + " ");
}
System.out.println();
}

After reading through the solution, I find there is a bug in my program. As follows:
INPUT: A tree (linked-list) 2 -> 3 -> -4 -> 3 -> 1 -> 2 and value = 5
EXPECTED OUTPUT: 2 ->3, 2 -> 3 -> -4 -> 3 -> 1 and 3 -> -4 -> 3 -> 1 -> 2
OUTPUT:  2 ->3 and 3 -> -4 -> 3 -> 1 -> 2.
The problem is that after we find a path like 2 -> 3, we should not stop right there. If so, we will miss the path like 2 -> 3 -> -4 -> 3 -> 1.
CORRECTION: Discard the ‘else’ block in line 16 and 21.

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b55a5eea2592', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b55a5eea25bc',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b55a5eea25be',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});