Career cup book question 4.8 - 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.
Answer given in career cup book -
Let’s approach this problem by simplifying it. What if the path had to
start at the root? In that case, we would have a much easier problem:
Start from the root and branch left and right, computing the sum thus far
on each path. When we find the sum, we print the current path. Note that we
don’t stop just because we found the sum. Why? Because we could have the
following path (assume we are looking for the sum 5): 2 + 3 + –4 + 3 + 1 +
2. If we stopped once we hit 2 + 3, we’d miss several paths (2 + 3 + -4 + 3
+ 1 and 3 + -4 + 3 + 1 + 2). So, we keep going along every possible path.
Now, what if the path can start anywhere? In that case, we make a small
modification. On every node, we look “up” to see if we’ve found the sum.
That is—rather than asking “does this node start a path with the sum?,” we
ask “does this node complete a path with the sum?”
1 void findSum(TreeNode head, int sum, ArrayList<Integer> buffer,
2 int level) {
3 if (head == null) return;
4 int tmp = sum;
5 buffer.add(head.data);
6 for (int i = level;i >- 1; i--){
7 tmp -= buffer.get(i);
8 if (tmp == 0) print(buffer, i, level);
9 }
10 ArrayList<Integer> c1 = (ArrayList<Integer>) buffer.clone();
11 ArrayList<Integer> c2 = (ArrayList<Integer>) buffer.clone();
12 findSum(head.left, sum, c1, level + 1);
13 findSum(head.right, sum, c2, level + 1);
14 }
15
16 void print(ArrayList<Integer> buffer, int level, int i2) {
17 for (int i = level; i <= i2; i++) {
18 System.out.print(buffer.get(i) + “ ”);
19 }
20 System.out.println();
21 }
My question - I think the algorithm needs some changes.
If we consider the following simple tree
-----------1
-----2----------3
If i want to search for path whose sum is 6 then it will not work because
at for right child we are not passing the value of left child? Can some one
explain me how this is going to work and what changes we need for the
algorithm mentioned above.
Thanks in advance.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
