# Find all the paths of tree that add to a input value

This code is attributed to Stack Overflow itself here. The path which adds to the sum, which need not be starting from the root, not be ending at the leaf, i.e. a path can be between root and a leaf.

I'm looking for code review, optimizations and best practices. I'm also looking for a solution better than $O(n^2)$ time complexity, if such exists. I'm also verifying space complexity to be $O(n)$, where $n$ in both the cases is the number of treenodes.

Also, the code specifically demands me to print, making unit testing not possible. Are there any pointers on how such code could be tested?

public class AllPathsAddingSum {

private TreeNode root;

create (items);
};

/**
* Constructs a binary tree in order of elements in an array.
* After the number of nodes in the level have maxed, the next
* element in the array would be a child of leftmost node.
*/
private void create(List<Integer> items) {
if (items.size() == 0) {
throw new IllegalArgumentException("There should atleast be single item in the tree");
}

root = new TreeNode(items.get(0));

final Queue<TreeNode> queue = new LinkedList<TreeNode>();

final int half = items.size() / 2;

for (int i = 0; i < half; i++) {
if (items.get(i) != null) {
final TreeNode current = queue.poll();
final int left = 2 * i + 1;
final int right = 2 * i + 2;

if (items.get(left) != null) {
current.left = new TreeNode(items.get(left));
}
if (right < items.size() && items.get(right) != null) {
current.right = new TreeNode(items.get(right));
}
}
}
}

private static class TreeNode {
private TreeNode left;
private int item;
private TreeNode right;

TreeNode(int item) {
this.item = item;
}
}

/**
* Prints all the paths that add to the input value.
* @param value the value, that all the nodes of a path should add upto.
*/
public void printAllSumPaths(int value) {
traverse(root, value);
}

private void traverse(TreeNode node, int value) {
if (node == null) return;

computePaths(node, 0, value, new ArrayList<Integer>());

traverse(node.left, value);
traverse(node.right, value);
}

private void computePaths(TreeNode node, int sum, int value, List<Integer> path) {
if (node == null) return;

sum = sum + node.item;

if (sum == value) {
for (Integer i : path) {
System.out.print(i + " ");
}
System.out.println();
}

computePaths(node.left, sum, value, path);
computePaths(node.right, sum, value, path);

path.remove(path.size() - 1);
}

public static void main(String[] args) {
sumPaths.printAllSumPaths(4);

sumPaths = new AllPathsAddingSum(Arrays.asList(1, 0, 0, -1));
sumPaths.printAllSumPaths(0);
}
}

• solution for unit-testing added Jan 26, 2015 at 8:29

public AllPathsAddingSum(List<Integer> items) {
create (items);
};


Unneeded space, unneeded semicolon. Consider autoformatting your code.

for (Integer i : path) {
System.out.print(i + " ");
}
System.out.println();


This section in computePaths is doing something different than the function description. It doesn't calculate, it prints.

Move it to a separate method. Then give the class a PrintStream to use. This PrintStream would be System.out, or a dummy PrintStream that just copies everything to an internal buffer.

Then you can unittest your code.