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) {
		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();
	}

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: