28 Sep 2016

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 !! :)

10 comments:

  1. There may be great increase in market research understanding that has become the sole guiding factor for each of the ways of
    advertising. If your unit isn't modular, contact the
    organization before you make any structural changes.
    This includes, brochures, flyers, business cards, order forms, price sheets and press kits.


    my web-site :: display for trade show

    ReplyDelete
  2. From small, mom and pop shops all of the way through to heavily established market leaders, every year businesses in most industry and of every size make the decision to participate of these important promotional events.
    Or you may simply have facts about a related field that your
    target audience would find interesting. Also, checking
    together with the business running the event can provide further
    information on whom to make use of and whether you'll find discounts agreed to participating businesses.



    My web-site - chicago trade show exhibits

    ReplyDelete
  3. Smaller exhibits, including tables, kiosks and some portable and modular inline
    displays, are beneficial for companies that desire a high-quality exhibit
    with consistent brand presentation at budget-friendly prices.
    Becoming a great designer requires that you think like one and
    have all the tools that certain would use. If the client had to get
    a display, it could either have to be a one-size-fits-all
    model, or they might have to purchase a number of different sized exhibits.


    Here is my homepage: trade show display graphics

    ReplyDelete
  4. A person necessarily assist to make significantly posts I might state.
    This is the first time I frequented your web page and
    to this point? I surprised with the analysis you made to create this particular publish extraordinary.
    Wonderful activity!

    Check out my blog :: company jets

    ReplyDelete
  5. This blog was... how do you say it? Relevant!! Finally I have found something which helped me.
    Thank you!

    My blog post :: the best private jets

    ReplyDelete
  6. I think this is among the most significant information for me.
    And i'm glad reading your article. But should remark on some general things, The
    web site style is great, the articles is really nice
    : D. Good job, cheers

    my website - search engine ranking

    ReplyDelete
  7. probably, I can replace ,
    if(leftFlag || rightFlag )
    return true;

    return false;

    with only, return (leftFlag || rightFlag);

    ReplyDelete
  8. probably, I can replace ,
    if(leftFlag || rightFlag )
    return true;

    return false;

    with only, return (leftFlag || rightFlag);

    ReplyDelete
  9. This blog was... how do you say it? Relevant!! Finally I have found something which helped me.
    Thank you!
    gclub casino
    golden slot mobile
    gclub

    ReplyDelete