package com.sunny.grokkingalgorithms.fasttrack.treesandgraphs;

import com.sunny.grokkingalgorithms.ctci.c4.util.BinaryTreeNode;
import com.sunny.grokkingalgorithms.ctci.c4.util.TreeUtils;

/**
 * Created by sundas on 6/10/2018.
 */
public class FindIfSumExistsFromRootToLeaf {

  /*
  Find if a path exists from root to leaf with
  a given sum.
   */

  /**
   *
   * @param root
   * @param sum
   * @param path
   * @param curSum
   */
  public static void findIfPathExistsFromRootToLeaf(BinaryTreeNode root,
                                                    int sum,
                                                    String path,

                                                    int curSum){
    /*
    Base case
     */
    if(root == null){
      return;
    }
    curSum += root.data;
    path += root.data +",";
    /*
    Check if path found since we have found a leaf node
     */
    if(root.left ==  null
        && root.right == null){
      if(curSum == sum){
        System.out.println(path);
      }
      return;
    }
    /*
    Keep looking, since we have not foun a leaf noce
     */
    else{
      findIfPathExistsFromRootToLeaf(root.left,sum,path,curSum);
      findIfPathExistsFromRootToLeaf(root.right,sum,path,curSum);
    }
  }

  /**
   *
   * @param args
   */
  public static void main(String[] args) {
    BinaryTreeNode root = TreeUtils.createBST();
    TreeUtils.performBfsLevelMarker(root);
    System.out.println("#######################");
    findIfPathExistsFromRootToLeaf(root, 37, "", 0);
    findIfPathExistsFromRootToLeaf(root,18,"",0);
    findIfPathExistsFromRootToLeaf(root,19,"",0);
    findIfPathExistsFromRootToLeaf(root,24,"",0);
    findIfPathExistsFromRootToLeaf(root,10,"",0);
  }

}

@@ -346,16 +346,1096 @@
 %0A   */%0A%0A
+  /**%0A   *%0A   * @param root%0A   * @param sum%0A   * @return%0A   */%0A  public static boolean findIfAPathExistsFromRootToLeafAlternate(BinaryTreeNode root,%0A                                                                 int sum)%7B%0A    /*%0A    Might not need this%0A     */%0A    if(root == null)%7B%0A      return false;%0A    %7D%0A    /**%0A     * subtract current root's value from sum%0A     */%0A    sum -= root.data;%0A    /*%0A    Found child node%0A     */%0A    if(root.left == null%0A        && root.right == null)%7B%0A      /*%0A      Time to check if path exists%0A       */%0A      if(sum == 0)%7B%0A        /*%0A        Remember to print this node as well.%0A         */%0A        System.out.print(root.data + %22 %22);%0A        return true;%0A      %7D%0A      return false;%0A    %7D%0A    boolean lFound = findIfAPathExistsFromRootToLeafAlternate(root.left,sum);%0A    if(lFound)%7B%0A      System.out.print(root.data + %22 %22);%0A    %7D%0A    boolean rFound = findIfAPathExistsFromRootToLeafAlternate(root.right,sum);%0A    if(rFound)%7B%0A      System.out.print(root.data + %22 %22);%0A    %7D%0A    /*%0A    Crucial check%0A     */%0A    return (lFound %7C%7C rFound);%0A  %7D%0A%0A
   /**%0A  
@@ -1487,16 +1487,16 @@
 am path%0A
-
    * @pa
@@ -2804,15 +2804,482 @@
 oot,
+ 
 10,
+ 
 %22%22,
-0
+ 0);%0A    System.out.println(%22##########################%22);%0A    findIfAPathExistsFromRootToLeafAlternate(root, 37);%0A    System.out.println();%0A    findIfAPathExistsFromRootToLeafAlternate(root, 18);%0A    System.out.println();%0A    findIfAPathExistsFromRootToLeafAlternate(root, 19);%0A    System.out.println();%0A    findIfAPathExistsFromRootToLeafAlternate(root, 24);%0A    System.out.println();%0A    findIfAPathExistsFromRootToLeafAlternate(root, 10);%0A    System.out.println(
 );%0A 

Find path from root to leaf without using string concatenation and extra variable. O(N)