Trees: Prune Sum Path

Problem Statement:
      Remove the paths from root to leaf whose sum is not equal to given K.

Given Sum = 15 = K
Source Code

Solution:


Valid paths with given sum :
 1 - > 2 - > 4 - > 8
and 1 - > 3 - > 6 - > 5

Bottom - up approach is being used to prune to the tree.

Below is the implementation.

 public static boolean prunePath(Node root, int givenSum , int currSum)
 {
  if(root==null) {
   if(givenSum==currSum)
    return true;
   else  
    return false;
  }
  
  boolean leftFlag = prunePath(root.left , givenSum , currSum+root.data);
  
  boolean rightFlag = prunePath(root.right , givenSum , currSum+root.data);
  
  if(!leftFlag)
   root.left=null;
  if(!rightFlag)
   root.right=null;
  
  return (leftFlag || rightFlag ) ;
   
 }

Please post your comments and suggestions.
Happy Coding !! :)

Post #123 : Eating Fish Problem

Problem Statement :

Below given are two arrays indicating the size of the arrays and the direction in which they are moving. A bigger fish can eat a smaller fish if they are moving in opposite direction.

Two fishes moving in same direction cannot eat each other because all the fishes are moving at a constant speed. Print the output of the fishes which survives

Fishes with distinct sizes and with their direction of movement from their current index

10

11

8

5

3

4

6

9

2

1

7

<--

<--

-->

-->

-->

<--

<--

<--

<--

<--

-->

Output : 

10	11	9	3	1	7
<--	<--	<--	<--	<--	-->

Explanation of output: 

Fishes with size 10 and 11 won't collide hence escapes, 

4 eats 3,  5 eats 4 , 6 eats 5 , 8 eats 6 , 9 eats 8,  then 2 and 1 survives because their behind bigger fish 9. Fish 7 survives because from its current position it will not collide with any other fish , hence the output.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

import java.util.Stack; /** * Bigger fisehes eat smaller ones , in diff direction , * No Fish Eats any other fish of same direction. * Assume all fish sizes are different * @author prateek */ public class EatFishProblem { public static void main(String[] args) { int[] arr1 = {10, 11, 8, 5, 3, 4, 6, 9, 2, 1 , 8} ; int[] dir1 = {-1, -1, 1, 1, 1, -1, -1, -1, -1, -1 , 1} ; solve(arr1,dir1); } static boolean solve(int[] arr,int[] dir){ Stack<Integer> rightDir = new Stack<Integer>(); Stack<Integer> leftDir = new Stack<Integer>(); int i = 0; //Skip all fishes moving to left in the beggining while(dir[i]!=1){ printFish(arr[i],dir[i]); i++; } int len = arr.length ; while(i<len){ if(dir[i] ==1 ) rightDir.push(arr[i]); else leftDir.push(arr[i]); eatFish(leftDir,rightDir); //if Fishes are empty in right stack, print fishes of the left stack //because these fishes moving to the left wont ever collide with subsequent fishes moving the right if(rightDir.isEmpty()) printStackInReverse(leftDir,-1); i++; } //Print Fishes moving the right first printStackInReverse(rightDir,1); printStackInReverse(leftDir,-1); return false; } /** Print stack in reverse order */ static void printStackInReverse(Stack<Integer> stack, Integer direction) { if(stack.isEmpty()) return ; Stack<Integer> temp = new Stack<Integer>(); while (!stack.isEmpty()) temp.push(stack.pop()); while (!temp.isEmpty()) printFish(temp.pop(), direction); } /** Eats fish from the stacks , depending on size */ static void eatFish(Stack<Integer> left, Stack<Integer> right){ while(!(left.isEmpty() || right.isEmpty())){ if(left.isEmpty() || right.isEmpty()) return ; else if(left.peek() > right.peek()) right.pop(); else if(left.peek() < right.peek()) left.pop(); else return ; } } static void printFish(int size, int direction){ System.out.println(direction == 1 ? size + "--> " : "<--"+size + " "); } }

Post your comments and suggestions if any.
Happy Coding :)