Hey Swathi,
The problem does mention any path but refers to "straight" paths along
a root to leaf path. Therefore, a path need not necessarily start from
the root or end with a leaf but should be along the path from the root
to a leaf.
On Nov 25, 4:05 am, Swathi <chukka.swa...@gmail.com> wrote:
> 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.
