Question

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.

Solution

Keep a list of items as buffer, and check the following condition:

“does this node complete a path with the sum?”

There’re n nodes in total, and the max size of buffer is lg(n), so the time complexity is O(nlgn).

Code

written by me

public static void find(TreeNode head, int target) {
	findSum(head, target, new ArrayList<Integer>());
}

private static void findSum(TreeNode node, int target, List<Integer> buffer) {
	if (node == null)
		return;

	buffer.add(node.data);
	int sum = 0;
	for (int i = buffer.size() - 1; i >= 0; i--) {
		sum += buffer.get(i);
		if (sum == target) {
			// from (i)th element until the last element is a valid path
			printPath(buffer, i);
		}
	}

	List<Integer> clone1 = new ArrayList<Integer>(buffer);
	findSum(node.left, target, clone1);

	List<Integer> clone2 = new ArrayList<Integer>(buffer);
	findSum(node.right, target, clone2);
}

private static void printPath(List<Integer> buffer, int start) {
	System.out.print("Path: ");
	for (int i = start; i < buffer.size(); i++) {
		System.out.print(buffer.get(i) + " ");
	}
	System.out.println();
}