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

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-all-paths-in-a-binary-tree-which-sum-upto-value/.

Problem

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.

Example
Consider a tree below:

       10
     /    \
    7      15
  /  \    /  \
 8    9  11   1

 input 
value = 16

output
7 - 9 - null
15 - 1 - null

Solution

Method 1 - Brute force and complete recursion
You might need to think about it for a second (I'm busy with other things), but this should basically run the same algorithm rooted at every node in the tree

public void printSums(Node n, int sum, int currentSum, String buffer) {
     if (n == null) {
         return;
     }
     int newSum = currentSum + n.val;
     String newBuffer = buffer + " " + n.val;
     if (newSum == sum) {
         System.out.println(newBuffer);
     }
     printSums(n.left, sum, newSum, newBuffer);
     printSums(n.right, sum, newSum, newBuffer);
     printSums(n.left, sum, 0, "");
     printSums(n.right, sum, 0, "");
} 

Runner call:

printSums(root, targetSum, 0, "");

Caveat - This function may fall into bottomless recursion, had this been a graph. So, it will work only for tree.
Here is code in java:

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) {
  String pathPart = (str.isEmpty() ? "" : str + " -> ")
    if (root == null)
        return;
    else if (root.getValue() == value) {
        System.out.println(pathPart + root);
    } else {
        printRecursively(root.getLeft(), value - root.getValue(),
                pathPart + root);
        printRecursively(root.getRight(), value - root.getValue(),
                pathPart + root);
    }
}

This is a good algorithm, but can be improved by making it iterative. One suspects that the interviewer is fishing for recursion here. Don't disappoint him!So, this is good answer when it comes to interview.

But lets look at better solution

Method 2 - Brute force but with some iteration

Here is code in java

public static void findSum(BinaryTreeNode<Integer> head, int sum,
        ArrayList<Integer> buffer, int level) {
    if (head == null)
        return;
    int tmp = sum;
    buffer.add(head.getValue());
    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();
}

References -stackoverflow, tianrunhe