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.

BinaryTreeFindSum.java

/* Travel the tree as well as save the node that exist on the path from the root to the current node, calculate
the sum from the current node to previous nodes to see if there exist a valid path */

public class BinaryTreeFindSum {
	private int depth(TreeNode root) {
		if(root == null) return 0;
		return Math.max(depth(root.left), depth(root.right)) + 1;
	}

	private void print(int[] path, int i, int j) {
		for(int k = i; k <= j; k++) {
			System.out.print(path[k] + " ");
		}
		System.out.println("");
	}

	private void Dfs(TreeNode node, int[] path, int level, int tar) {
		path[level] = node.val;
		int temp = 0;
		for(int i = level; i >= 0; i--) {
			temp += path[i];
			if(temp == tar) print(path, i, level);
		}

		if(node.left != null) Dfs(node.left, path, level+1, tar);
		if(node.right != null) Dfs(node.right, path, level+1, tar);

	}

	public void findSum(TreeNode root, int tar) {
		if(root == null) return;
		int dep = depth(root);
		int[] path = new int[dep];
		Dfs(root, path, 0, tar);
	}

	public static void main(String[] args) {
		TreeNode node1 = new TreeNode(1);
		TreeNode node2 = new TreeNode(0); node1.left = node2;
		TreeNode node3 = new TreeNode(-1); node2.left = node3;
		TreeNode node4 = new TreeNode(2); node2.right = node4;
		TreeNode node5 = new TreeNode(-2); node4.left = node5;
		TreeNode node6 = new TreeNode(3); node1.right = node6;
		TreeNode node7 = new TreeNode(4); node6.right = node7;
		TreeNode node8 = new TreeNode(-4); node6.left = node8;
		TreeNode node9 = new TreeNode(-8); node7.right = node9;
		TreeNode node10 = new TreeNode(-2); node7.left = node10;
		TreeNode node11 = new TreeNode(-6); node10.left = node11;
		BinaryTreeFindSum bt = new BinaryTreeFindSum();
		bt.findSum(node1, 1);
	}
}